如何讓這個腳本更快一點？

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

這花費了太多的時間。是否有可能讓它更快？如何讓這個腳本更快一點？

來源

2013-03-06 Александр Кривошеев

讓它只能走一半的範圍是多少？在xrange（1，600851475141/2）中，您不會找到任何超過值/ 2 ...的分隔符：' – ppeterka 2013-03-06 10:59:38

只檢查奇數 – gefei 2013-03-06 11:10:57

按2/4/8執行一個步驟並將代碼複製到循環。也稱爲非滾動。不知道它是否會給你任何速度，但有時會做更多的努力（但是在維護這些代碼方面需要更多的努力）。 – hakre 2013-03-06 12:31:47

對於小於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

來源

2013-03-06 11:11:49 unutbu

+1唯一的問題是如果數字是完美的正方形，那麼平方根將被打印兩次。 – Volatility 2013-03-06 11:19:23

@Volatility：感謝您的更正！ – unutbu 2013-03-06 11:23:40

恩，你可以通過只迭代素數來進一步優化它嗎？準備n組素數是相對容易的。如果你需要爲許多N解決問題，這是唯一值得的努力。但是我相信你可以將複雜性從'sqrt（N）'降到'log（sqrt（n））'。或者我錯了？ – luk32 2013-03-06 13:24:20

如何讓這個腳本更快一點？

回答

相關問題