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.

有办法进一步完善，但是，这个优化对于这个简单的问题，单独应该足够了。