Python 函数如果 2 个整数互质则 returns 为真

Question

我需要一些帮助来找出我在这个函数中的错误：


def is_coprime(num_1, num_2):
    """Function that returns true if 2 integers are coprime. """
    if num_1 > num_2:
        small = num_2
    else:
        small = num_1
    for i in range(1, small + 1):
        if ((num_1 % i == 0) and (num_2 % i != 0)):
            gcd = i
        if (gcd == 1):
            return True
        else:
            return False

希望缩进不是那么糟糕。我认为我的错误在于 if 条件，但我想不通是什么。

Answer 1

我建议采用这种方法：

def divisors(x):
    return {i for i in range(2, x//2 + 1) if not x % i}

def coprime(x, y):
    return divisors(x).isdisjoint(divisors(y))

它是如何工作的？ divisors(x) returns 集合 f 所有大于 1 的数的约数。 coprie(x, y) 函数检查给定的集合是否不相交。

Answer 2

互质可以用 math.gcd 像这样完成：

import math

def is_coprime(x, y):
    return math.gcd(x, y) == 1

is_coprime(39, 115)
True

is_coprime(115*89,115)                                                                                                                             
False

Answer 3

我会说你的算法很糟糕。让我们来看一个简单的例子，首先假设：

num_1 = 2
num_2 = 3
small = 2

运行这些值通过你的循环：

for i in range(1, small + 1):
    if num_1 % i == 0 and num_2 % i != 0:
        gcd = i

第一次迭代：

i = 1
2 % 1 == 0 and 3 % 1 == 0

第二次（也是最后一次）迭代：

i = 2
2 % 2 = 0 and 3 % 2 != 0
    gcd = 2

回答错误！ gcd(2, 3) == 1

假设您不想像@oppressionslayer 建议的那样使用 built-in math.gcd()，我们可以在维基百科中查找 GCD 并使用 recursive binary algorithm。由于我们只想知道数字是否互质，我们可以简化该算法中的一个语句（even-even 测试）并简单地 return False:

def coprime(u, v):

    # simple cases (termination)
    if u == v:
        return u == 1

    if u == 0:
        return v == 1

    if v == 0:
        return u == 1

    # look for factors of 2
    if ~u & 1:  # u is even
        if v & 1:  # v is odd
            return coprime(u >> 1, v)

        return False

    if ~v & 1:  # v is even, u is odd
        coprime(u, v >> 1)

    # reduce larger argument
    if u > v:
        return coprime(u - v, v)

    return coprime(v - u, u)

一些简单的测试：

print(coprime(2, 3))  # True
print(coprime(21, 24))  # False
print(coprime(39, 115))  # True
print(coprime(115*89, 115))  # False

Python 函数如果 2 个整数互质则 returns 为真

Python function that returns true if 2 integers are coprime

python

primes

number-theory