爲什麼此代碼需要8分鐘才能完成？

這是一個（非常糟糕的）解決項目歐拉問題之一。問題是找到10_001st素數。下面的代碼是這樣做的，但需要8分鐘才能運行。你能解釋爲什麼是這種情況，以及如何優化它？爲什麼此代碼需要8分鐘才能完成？

primes = [] 
number = 2.0 

until primes[10000] != nil 
    if (2..(number - 1)).any? do |n| 
    number % n == 0 
    end == false 
    primes << number 
    end 
    number = number + 1.0 
end 

puts primes[10000]

來源

2013-03-18 oFca

'if enumeration.any？{} == false' =>'if enumeration.none？{}' – oldergod 2013-03-18 00:07:04

一些簡單的主要發現的優化：

首先將2推入素數列表，然後檢查3是否爲素數。（這消除了編寫0到2的特殊情況代碼的需要）
您只需檢查主要候選人的奇數。（或者，如果您開始添加2/3/5並檢查7，則只需在執行％6之後檢查數字是1或5即可。或者...您明白了）
您只有看看你的當前候選x是整除因素最多的sqrt（x） - 因爲上述sqrt(x)分歧X任何因素成數低於sqrt(x)，而您已經檢查了所有這些的。
您只需檢查x除數的素數列表中的數字，而不是所有數字，因爲所有複合數字都可以被素數整除。例如，81是9 * 9 - 但9 * 9是3 * 3 * 9，9是複合的，所以當您檢查3時，您會發現它是一個質數。因此，您無需測試9是否是一個因子等等每個複合因素。

有非常優化，加速了黃金的發現功能（見Sieve of Atkin一開始），但這些都是常見的優化，很容易拿出。

來源

2013-03-18 00:17:30 Patashu

你真的要檢查數字是否與以前的所有數字相除？只檢查你已經發現的小素數。另外，爲什麼使用浮點數的整數是完美的罰款？

編輯：

一些可能的變化（不是最好的算法，可提高）：

primes = [2, 3, 5] 
num = 7 

until primes[10000] 
    is_prime = true 
    i = 0 
    sqrtnum = Math.sqrt(num).ceil 
    while (n=primes[i+=1]) <= sqrtnum 
    if num % n == 0 
     is_prime = false 
     break 
    end 
    end 
    if is_prime 
    primes << num 
    end 
    num += 2 
end 

puts primes[10000]

在我的電腦（1000質數）：

Yours: 
real 0m3.300s 
user 0m3.284s 
sys  0m0.000s 

Mine: 
real 0m0.045s 
user 0m0.040s 
sys  0m0.004s

來源

2013-03-18 00:06:03

不確定只檢查你已經發現的較小素數就足夠了 – DavidC 2013-03-18 00:40:44

DavidC：會的。想一想：如果數字不能被小於它自己的任何素數整除，它也不能被任何兩個或更多這些素數的任何積分。另外一個含義是，你只需要檢查不大於被檢查數字的平方根的素數。 – Mchl 2013-03-18 01:45:32

爲什麼此代碼需要8分鐘才能完成？

回答

相關問題