查找数字优化的所有除数

Question

我编写了以下函数,它找到给定自然数的所有除数,并将它们作为列表返回:

def FindAllDivisors(x):
    divList = []
    y = 1
    while y <= math.sqrt(x):
        if x % y == 0:
            divList.append(y)
            divList.append(int(x / y))
        y += 1
    return divList

它的效果非常好,除了当输入是一个18位数字时它真的很慢.你对我如何加快它有什么建议吗？

更新:

我有以下方法来检查基于费马小定理的素数:

def CheckIfProbablyPrime(x):
    return (2 << x - 2) % x == 1

检查单个数字时,此方法非常有效,但是我不确定是否应该使用它来编译所有素数到一定的边界.

Answer 1

您可以通过计算素数因子来找到数字的所有除数.每个除数必须是因式分解中素数的组合.

如果你有一个素数列表,这是一个简单的分解方法:

def factorize(n, primes):
    factors = []
    for p in primes:
        if p*p > n: break
        i = 0
        while n % p == 0:
            n //= p
            i+=1
        if i > 0:
            factors.append((p, i));
    if n > 1: factors.append((n, 1))

    return factors

这称为试验分裂.有更有效的方法来做到这一点.请参阅此处以获取概述.

计算除数现在非常简单:

def divisors(factors):
    div = [1]
    for (p, r) in factors:
        div = [d * p**e for d in div for e in range(r + 1)]
    return div

计算所有除数的效率取决于找到素数的算法(这里是小概述)和分解算法.对于非常大的数字而言,后者总是很慢,而且你无能为力.