时间戳

首页 > 解决方案 > 如何使用 Python 提高从 2 到 N 的数字查找 N 是否为 Coprime 的时间复杂度？

python - 如何使用 Python 提高从 2 到 N 的数字查找 N 是否为 Coprime 的时间复杂度？

问题描述

我已经编写了我的代码，它包含 2 种方法coprime()来检查 2 个数字是否互质，并count_coprime()计算与之互质的数字n并且它可以工作，但是它太慢了，我正在寻找改进：

第一个：

def coprime(a, b):
    # Returns a boolean value
    # Returns true if a and b are in fact coprime
    if a == 1 or b == 1:
        return True
    else:
        count = 0
        if a < b:
            for i in range(2, a + 1):
                if a % i == 0:
                    if b % i == 0:
                        count += 1
        else:
            for i in range(2, b + 1):
                if b % i == 0:
                    if a % i == 0:
                        count += 1
        return count < 1

第二：

def count_coprimes(n):
    count = 1
    for i in range(2, n):
        if coprime(i, n):
            count += 1
    return count

标签： pythonperformancemathtime-complexity

解决方案

要检查两个数是否互质，可以使用 GCD（Great Common Diviso r）算法。如果gcd(a,b)==1，则值互质。它O(max(log(a),log(b)))及时有效，因此整体复杂性是O(nlogn)

请注意，标准数学模块已经包含math.gcd()函数。欧几里得算法的简单实现：

def EuclideanGCD(x, y): 
    while y: 
        x, y = y, x % y 
    return x

推荐阅读