python - 返回没有公因数的数字

Question

问题如下：

创建一个接受 2 个输入、一个数字n和一个列表的函数lst。该函数应返回一个列表，其中lst包含与n（1 除外）没有共同因子的所有数字。n 和 中的所有数字 lst均为大于或等于 0 的正整数。

我的尝试

def no_common_factors (n, lst):

    def uf(n):  #get a set of factors
        factors = []
        i = 2
        while n > 1: 
            if n % i == 0: 
                factors += [i]
                n = n / i
            else: 
                i += 1
        return set(factors)

    factors_n = uf(n)
    no_common = []

    for i in range(0, len(lst)): 
        factors_i = uf(i)
        if factors_n.isdisjoint(factors_i): 
            no_common += [lst[i]]
        else: 
            continue

    return no_common

不起作用：

In [41]: no_common_factors(15, [72,27,32,61,77,11,40])
Out[41]: [72, 27, 32, 77]

当它应该返回 [32, 61, 77, 11] 时。

我盯着它，但看不出我做错了什么，它应该很简单。请帮忙！

Answer 1

我会使用它math.gcd返回两个数字的最大公约数：

import math

def no_shared_factors(num, items):
    return [item for item in items if math.gcd(item, num) == 1]

输出正确的结果：

>>> no_shared_factors(15, [72, 27, 32, 61, 77, 11, 40])
[32, 61, 77, 11]

如果math.gcd黑盒太多，您可以编写自己的实现或查看代码math（请参阅Python 中的最大公约数代码）：

def gcd(a, b):
    """
    Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a % b
    return a

请查看Wikipedia上的 GCD 页面，了解更多替代算法。