ruby - Ruby 中的 Project Euler #3

Question

欧拉计划问题#3:

13195的质因数是5、7、13、29。600851475143的最大质因数是多少？

def is_prime?(number)
    prime = true
    (2...number).each { |x|
        prime = false if number % x == 0
    }
    prime
end

def largest_prime(number)
    primes = []
    (number.downto(1)).each {|x|
        primes.push(x) if number % x == 0 && is_prime?(x)
        break if primes.count == 1
    }
    primes[0]
end

我的答案是用 Ruby 写的。该代码适用于较小的数字但不适用于较大的数字，谁能解释到底发生了什么以及如何解决它？我见过其他人遇到过这个问题——很抱歉重新发布——但我是一个编程新手，我并不真正理解他们的答案，也没有看到任何其他用 Ruby 回答的帖子。谢谢!

Answer 1

这里有一些帮助您提高代码性能的建议(假设您的测试编号是n):

• 只执行从 2 到 square_root(n) 的可除性测试。在此范围内，任何大于 square_root(n) 的数字都已包含在内。从数学角度思考 :)
• 任何不是 2 的偶数都不是质数!
• 使用 prime sieve大大提高主要测试算法的性能。

但是，不要这样做:

• 由于您是为了娱乐和学习而解决欧拉问题，因此请勿使用 ruby​​ 提供的 prime 库。

这是我用来解决这个问题的两个帮助器(我很久以前就在我刚接触 ruby​​ 时写了它们，可能效率不高，例如它们不使用 sieve我建议):

def lower_divisors_of(n)
  data = (2..(Math.sqrt(n).to_i)).select{ |a| n % a == 0 }
  data.map{|a| [a, n/a]}.flatten.sort.reverse
end

def is_prime?(n)
  lower_divisors_of(n).empty?
end

lower_divisors_of(n).detect{|i| is_prime?(i)}