如何让这个脚本更快一点？

Question

for i in xrange(1, 600851475141):
  if 600851475141 % i == 0:
    print i

这花费了太多时间.有可能让它更快吗？

Answer 1

对于每个小于的除数sqrt(N),有一个大于的除数sqrt(N).所以你只需要找到i小于的除数,sqrt(N)并计算互补除数N//i.

import math
N = 600851475141
divisors = []
for i in xrange(1, int(math.sqrt(N))+1):
    if N % i == 0:
        divisors.extend(set((i, N//i)))
for d in sorted(divisors):
    print(d)

产量

1
3
11981
35943
16716787
50150361
200283825047
600851475141