Chương trình đếm số ước chung của hai số trong Python

Giả sử chúng ta có hai số a và b. Chúng ta phải tìm có bao nhiêu số nguyên dương là ước của cả a và b.

Vì vậy, nếu đầu vào là a = 288 b = 240, thì đầu ra sẽ là 10 vì các ước chung là [1,2,3,4,6,8,12,16,24,48].

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:

• res := 0
• với i từ 1 đến gcd(a, b) + 1, thực hiện
  • nếu (a mod i) bằng 0 và (b mod i) bằng 0, thì res := res + 1
• trả về res

Ví dụ

Hãy xem triển khai sau để hiểu rõ hơn:

from math import gcd
def solve(a, b):
    res = 0
    for i in range(1, gcd(a,b)+1):
        if (a % i) == 0 and (b % i) == 0:
            res += 1
    return res

a, b = 288, 240
print(solve(a, b))

Đầu vào

288, 240

Đầu ra

10