Ruby項目中的Euler＃3解決方案超時

Question

我正在通過一些Project Euler問題來練習使用Ruby解決問題。我爲問題3提出了以下解決方案，儘管它適用於較小的數字，但似乎從未爲較大的數字返回值。這是因爲與Bignum有關嗎？有人可以給我描述爲什麼它超時，並更好的辦法來解決這個問題（最好用推理/上發生了什麼事情的幕後我試圖信息瞭解）

項目歐拉問題：

13195的主要因素是5,7,13和29. 數字600851475143的最大素因是多少？

我的解決辦法：

def primecheck(number) 
    (2...number).each { |x| return false if number % x == 0} 
    true 
end 

def largestprime(number1) 
    factors = [] 
    (1..number1).each do |i| 
     if number1 % i == 0 && primecheck(i) 
     factors << i 
     end 
    end 
puts "The answer is #{factors.last}" 
end 

largestprime(600_851_475_143) 

Answer 1

它是通過所有的數字會從1到600851475143.它也可以檢查，如果數是素數，對於所有的數字。所以總的操作次數是O（n^3/2），應該在10^18左右。預計這需要花費數年的時間。您應該更改算法，使漸近複雜度降低

Answer 2

提示：一旦找到主要因素，您可以用它除以。這大大減少了您必須檢查的剩餘潛在因子的範圍。

使用您的第一個例子：

13195/5 = 2639, 
2639/7 = 377, 
377/13 = 29, 
29/29 = 1, done. 

這樣，我們只需要檢查達29，而不是一路13195.

有辦法進一步完善，但是，這個優化對於這個簡單的問題，單獨應該足夠了。