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

Question

问题如下:

Create a function that takes 2 inputs, a number n and a list lst. The function should return a list of all the numbers in lst that share no common factors with n (other than 1). n and all numbers in lst will be positive integers greater than or equal to 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 代码(参见 Code for Greatest Common Divisor in 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 页面用于更多替代算法。