我编写了以下函数,它查找给定自然数的所有除数并将它们作为列表返回:
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
这种方法在检查单个数字时非常有效,但是我不确定是否应该使用它来编译所有素数到某个边界。
我会做一个素因子分解,然后从结果中计算出所有的因子。
你可以通过计算素数分解来找到一个数的所有除数。每个除数必须是因子分解中素数的组合。
如果你有一个素数列表,这是一个简单的分解方法:
这叫审判庭。有很多更有效的方法可以做到这一点。有关概述,请参见here。
现在计算除数很容易:
计算所有因子的效率取决于寻找素数的算法(小概图here)和因子分解算法。后者对于很大数量的数据总是很慢,对此你无能为力。
我建议将
math.sqrt(x)
的结果存储在一个单独的变量中,然后对照它检查y
。否则将在while
的每个步骤重新计算,并且math.sqrt
绝对不是轻量级操作。相关问题 更多 >
编程相关推荐