3

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

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

这种方法在检查单个数字时非常有效，但是我不确定是否应该使用它来编译所有素数到某个边界。

4

4 回答 4

25

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

如果您有一个素数列表，这是一种获得分解的简单方法：

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

计算所有除数的效率取决于找到素数的算法（这里的小概述）和分解算法。对于非常大的数字，后者总是很慢，对此您无能为力。

于 2012-09-14T09:47:10.617 回答
3

我建议将结果存储math.sqrt(x)在一个单独的变量中，然后y对其进行检查。否则每一步都会重新计算，while绝对math.sqrt不是轻量级的操作。

于 2012-09-14T09:44:41.940 回答
1

我会做一个素因子分解，然后根据该结果计算所有除数。

于 2012-09-14T09:48:20.397 回答
0

我不知道是否有很大的性能影响，但我很确定强制转换为 int 是不必要的。至少在 Python 2.7 中，int x / int y返回一个 int。

于 2012-09-14T09:48:26.167 回答