时间戳

首页 > 解决方案 > 如何让这段代码更快地找到大数的自然除数？

python - 如何让这段代码更快地找到大数的自然除数？

问题描述


a = int(input())
f = 0
for i in range(1, a + 1):
    if a % i == 0:
        f += 1
print(f)

此代码找到数字 a 的自然因数的数量，如何使其更快地处理大数？

标签： python

解决方案

您可以通过累积构成数字的素数组合来调整素数因子算法来计算除数。如果 N 是一个素数，这仍然需要 (√N)/2 次迭代，但是当 N 有许多素数时，它会大大减少迭代次数。

def divCount(N):
    result = 1
    p,inc  = 2,1
    while p*p<=N:
        d = 1
        while N%p == 0:
            d  += 1
            N //= p
        result *= d
        p,inc   = p+inc,2
    if N>1: result *= 2
    return result

输出（全部小于 2 毫秒）：

divCount(12) --> 6

divCount(479001600) --> 792

divCount(479001599) --> 2    # prime number (10,944 iterations)

推荐阅读