ruby - 加速 Ruby 中最大的质因数程序

Question

一个简单的程序，用于在 Ruby 中查找数字的最大质因数，由 2 个方法组成:

def is_prime?(n)
  (2..n).select {|number| n % number == 0}.length == 1 ? true : false
end

def prime_factors(number)
  (1..number).select {|m| number % m == 0 && is_prime?(m) == true}.max
end

它适用于像 100 这样的小数字。但是，我正在尝试解决 Project Euler 上的问题，它使用数字 600851475143。尝试这个问题时，问题甚至不会运行，我最终在大约 a 后取消了它分钟。

我怎样才能改变它来提高性能？

Answer 1

使用 Ruby 的 Prime#prime_division方法:

require 'prime'

Prime.prime_division(600851475143).max_by(&:first).first
  #=> 6857

三个步骤:

a = Prime.prime_division(600851475143)
  #=> [[71, 1], [839, 1], [1471, 1], [6857, 1]]
  # Note (71**1)*(839**1)*(1471**1)*(6857**1) #=> 600851475143  
b = a.max_by(&:first)
  #=> [6857, 1] 
b.first
  #=> 6857