python - 数字 : How can I improve this code to find the number of divisors of big numbers? 的除数

Question

当涉及非常大的数字时，我的代码非常慢。

def divisors(num):
    divs = 1
    if num == 1:
        return 1

    for i in range(1, int(num/2)):
        if num % i == 0:
            divs += 1
        elif int(num/2) == i:
            break
        else:
            pass
    return divs

对于 10^9，我得到的运行时间为 381.63s。

Answer 1

这是一种确定 n 的各种不同素因数的重数的方法。每个这样的幂 k 都会为除数总数贡献一个 k+1 因子。

import math

def smallest_divisor(p,n):
    #returns the smallest divisor of n which is greater than p
    for d in range(p+1,1+math.ceil(math.sqrt(n))):
        if n % d == 0:
            return d
    return n

def divisors(n):
    divs = 1
    p = 1
    while p < n:
        p = smallest_divisor(p,n)
        k = 0
        while n % p == 0:
            k += 1
            n //= p
        divs *= (k+1)
    return divs - 1

它返回真因数的数量(因此不计算数字本身)。如果您想计算数字本身，请不要从结果中减去 1。

它可以快速处理大小为 10**9 的数字，但处理更大的数字时速度会显着减慢。