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

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

使用你的第一个例子:

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

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

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