Ruby 解决方案中的 Project Euler #3 超时 [英] Project Euler #3 in Ruby solution times out

问题描述

我将通过几个 Project Euler 问题来练习使用 Ruby 解决问题.我为问题 3 提出了以下解决方案，虽然它适用于较小的数字，但它似乎永远不会为较大的数字返回值.这是因为与 Bignum 有关吗?有人可以向我描述为什么超时，以及解决此问题的更好方法(最好提供有关幕后情况的推理/信息.我正在尝试理解)

I'm going through a few of the Project Euler problems to practice problem solving using Ruby. I came up with the following solution for problem 3, and while it works for smaller numbers, it never seems to return a value for larger numbers. Is this because of something to do with Bignum? Can someone describe to me why it's timing out, and better way to solve this problem (preferably with reasoning/info on what's going on behind the scenes. I'm trying to understand)

欧拉项目问题:

13195 的质因数是 5、7、13 和 29.600851475143 的最大质因数是多少?

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 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)

推荐答案

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

Hint: Once you've found a prime factor, you can divide by it. This greatly reduces the range of remaining potential divisors you have to check.

使用您的第一个示例:

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

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

This way, we only had to check up to 29 instead of all the way to 13195.

有进一步改进的方法，但对于这个简单的问题，仅此优化就足够了.

There are ways to improve it further, but this optimization alone should be more than enough for this simple problem.

这篇关于Ruby 解决方案中的 Project Euler #3 超时的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！