python - 怎么求2个数的公因数

Question

打印 a 和 b 的公因数的个数。

输入 > 10, 15

输出 > 2

10、15的公因数是1和5

我的代码

def print_factors(x,y):
l = []
for i in range(1, x + 1):
    if x % i == 0:
        l.append(i)
m = []
for i in range(1, y + 1):
    if y % i == 0:
        m.append(i)
print (list(set(l).intersection(m)))
num1 = int(input("Enter a number: ")) #10
num2 = int(input("Enter a number: ")) #15
print_factors(num1,num2)

有没有更好的优化方法，比如列表理解。或使用 zip 模块

标签： pythonlist

Answer 1

显然 GCD 已经存在，所以其他答案可以修改为

from fractions import gcd
def cf(num1,num2):
    n=[]
    g=gcd(num1, num2)
    for i in range(1, g+1): 
        if g%i==0: 
            n.append(i)
    return n

print(cf(int(input("a:")),int(input("b:"))))

然后当然你可以使用素数测试中的“技巧”，并循环直到数字的平方根，因为除数成对出现：

from fractions import gcd
from math import sqrt
def cf(num1,num2):
    n=[]
    g=gcd(num1, num2)
    for i in range(1, int(sqrt(g))+1):
        if g%i==0:
            n.append(i)
            if g!=i*i:
                n.append(int(g/i))
    return n

print(cf(int(input("a:")),int(input("b:"))))