Project Euler #3 Ruby 解决方案 - 我的代码有什么问题？

Question

这是我的代码：

def is_prime(i)
    j = 2
    while j < i do 
        if i % j == 0
            return false
        end
        j += 1
    end
true
end

i = (600851475143 / 2)
while i >= 0 do 
    if (600851475143 % i == 0) && (is_prime(i) == true) 
        largest_prime = i
        break 
    end
    i -= 1
end



puts largest_prime

为什么不返回任何东西？遍历所有数字的计算量是否太大？有没有一种不使用 Ruby prime 库（违背目的）的简单方法？

我在网上找到的所有解决方案对我来说都太高级了，谁有初学者能够理解的解决方案？

Answer 1

我不会解决太多答案，而是解决您如何寻求答案。

最优雅的故障排除方法是使用调试器来深入了解实际发生的情况：How do I debug Ruby scripts?

就是说，我很少使用调试器——我只是在这里和那里坚持放置以查看发生了什么。

首先添加 puts "testing #{i}" 作为循环内的第一行。虽然屏幕 I/O 将比静默计算慢一百万倍，但它至少会让您确信它正在做您认为正在做的事情，并且也许可以深入了解整个问题需要多长时间。或者它可能会揭示错误，例如计数器未更改、向错误的方向递增、超过中断条件等。基本的健全性检查内容。

如果这没有引起灵感，请深入 puts 在 if 语句中。还没有爆料？接下来放入 is_prime()，然后放入 is_prime() 的循环。你明白了。

另外，在开发过程中，世界上没有理由从 600851475143 开始！ 17、51、100 和 1024 也可以。（并且不要忘记诸如 0、1、2、-1 之类的边缘情况，只是为了好玩。）这些都将在您的手指离开回车键之前完成——或者证明您的算法真的永远不会 returns 然后把你送回绘图板。

使用这两种方法，我相信您会在一两分钟内找到答案。祝你好运！

Answer 2

"premature optimization is (the root of all) evil"。 :)

在这里，您可以立即找到 (1) 最大的 (2) 质数因子。如何找到所有因子，不管是素数还是非素数，然后然后取最后一个（最大的）素数。当我们解决了那个，我们就可以开始优化了。

一个数 n 的因子 a 存在一些 b（我们假设 a <= b 以避免重复）a * b = n。但这意味着 a <= b 也将是 a*a <= a*b == n。

因此，对于每个 b = n/2, n/2-1, ...，潜在的对应因子自动称为 a = n / b，根本不需要测试 a 的可除性......也许你可以计算a 中的哪些也不必进行素数测试。

最后，如果p是n的最小质因数，那么n的质因数是p，[=25的所有质因数=].对吗？

现在你可以完成任务了。

更新： 你可以找到更多讨论和各种伪代码 here. Also, search for "600851475143" here on Stack Overflow.

Answer 3

你知道你可以用 Ruby 中的一行代码解决这个问题吗？

Prime.prime_division(600851475143).flatten.max

=> 6857

Project Euler #3 Ruby 解决方案 - 我的代码有什么问题？

Project Euler #3 Ruby Solution - What is wrong with my code?

ruby

primes

ruby-on-rails

factorization