python - 如何才能减少计算量？大量时效率很低

Question

num = input ()
fact = 0
while fact != num:
     fact = fact + 1
     rem = num % fact
     if rem == 0:
          print fact

Answer 1

您只需求输入数字的平方根即可获得所有因数(不像其他地方所建议的那样远到数字的一半)。例如，24 的因数为 1、2、3、4、6、8、12、24。sqrt(24) 约为 4.9。检查1也得到24，检查2也得到12，检查3也得到8，检查4也得到6。因为5>4.9，所以不用检查了。 (是的，我知道 24 不是最好的例子，因为所有小于 sqrt(24) 的整数都是 24 的因数。)

factors = set()
for i in xrange(math.floor(math.sqrt(x))+1):
    if x % i == 0:
        factors.add(i)
        factors.add(x/i)
print factors

有一些非常复杂的方法可以更好地处理大量数据，但这应该可以让您在运行时得到不错的改进。根据您的应用程序，缓存还可以为您节省大量时间。