Ước số chung
Xem PDF
Điểm:
100
Thời gian:
1.0s
Bộ nhớ:
640M
Input:
bàn phím
Output:
màn hình
Số nguyên dương \(p\) gọi là ước số chung của \(n\) 𝑣à \(m\) khi \(m\) 𝑣à \(n\) cùng chia hết cho \(p\).
Viết chương trình nhập vào một số nguyên dương \(n,m\) (\(n,m \leq 10^{7}\)).
Hãy in ra tất cả các ước số chung của \(n\) 𝑣à \(m\).
Input
- Nhập \(2\) số nguyên dương \(n,m\).
Output
- In ra các ước số chung của chúng.
Example
Test 1
Input
54 72 Output
1 2 3 6 9 18
Bình luận
import math
Hàm tính GCD của hai số a và b
def gcd(a, b):
while b:
a, b = b, a % b
return a
Nhập dữ liệu
n, m = map(int, input().split())
Tính GCD của n và m
g = gcd(n, m)
Tìm và in tất cả các ước số của GCD
result = []
for i in range(1, int(math.sqrt(g)) + 1):
if g % i == 0:
result.append(i)
if i != g // i: # Tránh in lại ước số lớn bằng ước số nhỏ
result.append(g // i)
Sắp xếp kết quả theo thứ tự tăng dần
result.sort()
In kết quả
print(" ".join(map(str, result)))
8 bình luận nữa