1

我正在通过一些 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)
4

2 回答 2

10

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

使用您的第一个示例：

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

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

有一些方法可以进一步改进它，但是对于这个简单的问题，仅此优化就已经足够了。

于 2013-05-10T02:58:39.530 回答
4

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

于 2013-05-10T02:46:19.763 回答