Ruby解决方案中的项目Euler#3超时

我正在经历一些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) 

提示:一旦找到了一个主要因素,你就可以除以它。 这大大减少了您必须检查的剩余潜在除数的范围。

使用你的第一个例子:

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

这样,我们只需要检查29而不是一直到13195。

有一些方法可以进一步改进它,但这种优化本身应该足以解决这个简单的问题。

它将通过从1到600851475143的所有数字。它还会检查所有数字的数字是否为素数。 所以操作总数为O(n ^ 3/2),应该在10 ^ 18左右。 预计计算时间需要数年。 您应该更改算法,以便渐近复杂度降低