加速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这样的小数字.但是,我正在尝试使用数字600851475143解决Project Euler上的问题.当尝试此问题时,问题甚至不会运行,我最终在大约一分钟后取消它.

如何改变这一点以提高性能？

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