我写了下面的功能，找到一个给定的自然数的所有约数，并返回它们作为一个列表进行了一些优化的所有除数：寻找
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
检查单号时，此方法是非常有效的，但是我不确定我是否应该用它来编译所有素数达到某个边界。
您可以通过计算素因子分解找到数字的所有除数。每个除数必须是因式分解中的素数的组合。
如果你有质数的列表，这是一种简单的方式来获得分解：
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
这就是所谓的审判庭。有很多更有效的方法来做到这一点。有关概览，请参阅here。
计算除数是现在很容易：
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
计算所有除数的效率取决于算法来寻找素数（小概述here），并在分解算法。后者总是很慢，非常大的数字，你可以做的事情不多。
我的第一个想法也是关于素数的因子，但我不确定他们的搜索是否更快，而不是直接将N除以所有数字 - 我们仍然会筛选直到sqrt（N），然后花O（ 1）对于每个素数的组合（我们仍然需要穿过它）。 –
我对我的问题添加了一个小修改。所以如果我使用我的当前素数测试，这是否足够有效，还是应该改变我的测试？ –
@Bob，主要列表可以预先计算，即使需要检查多个数字，也只能进行一次。分解的优点是只检查素数。对于一个数字你是对的，它并不重要。 –
我建议将结果math.sqrt(x)存储在一个单独的变量，然后检查y反对它。否则，将在每个步骤while和math.sqrt重新计算绝对不是轻量级操作。
也可以尝试将结果附加到字符串而不是列表。 –
这是代码优化，很好，但你会有相同的“大O”。 Ben Ruijl解决方案确实可以减少算法的复杂性，从而节省大数量的时间。 – MatthieuW
我会做素因子分解，然后从该结果计算所有除数。
我不知道是否有很多的性能命中，但我非常确定，转换为int是不必要的。至少在Python 2.7中，int x/int y返回一个int。
在Python 3中，它没有。在那里你可以使用'//'来进行地板划分。 –
您是否使用'CheckIfPrime'来查看是否可以跳过某个x的分区？你应该小心这一点，因为你可以得到误报：'CheckIfPrime'过滤大部分数字，但一些复合仍然会产生'真'！ –
@BenRuijl请给我一个例子，非常感谢！ –
由于[Fermat pseudoprimes]（http://en.wikipedia.org/wiki/Fermat_pseudoprime），您的'CheckIfPrime'函数不起作用。例如，'CheckIfPrime（341）'为True，但是341 = 11 * 31。如果'CheckIfPrime'为False，那么这个数字肯定是复合的，但是反过来并不成立。 [对不起，我错过了BenRuijl先前的评论。不过，如果仅将它用作“CheckIfProbablyPrime”，它仍可能有用。 – DSM