Speeding up greatest prime factor program in Ruby

Question

A simple program to find the greatest prime factor of a number in Ruby, made up of 2 methods:

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

It works fine for small numbers like 100. However, I'm trying to solve the problem on Project Euler, which uses the number 600851475143. When trying this the problem will not even run and I end up canceling it after about a minute.

How can I alter this to increase performance?

Answer 1

Use Ruby's Prime#prime_division method:

require 'prime'

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

Three steps:

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 

Answer 2

There is a way of factoring which is more efficient and which also finds only prime factors, eliminating the need to test for primeness. Skip to the end to see it or read through to see how I got there.

I refactored your solution so it would be easier to think about, extracting a factors method, removing unnecessary explicit uses of booleans and renaming some things:

def greatest_prime_factor(n)
  factors(n).select { |c| prime?(c) }.max
end

def factors(n)
  (1..n).select { |c| n % c == 0 }
end

def prime?(n)
  (2..n).count { |c| n % c == 0 } == 1
end

There is an inefficiency in factors: even after we know that a number c (for "candidate") is a factor, we test numbers greater than n/c. To fix that, when we find a factor, divide n by it before we look for the next factor:

def factors(n)
  if n == 1
    []
  else
    f = (2..n).find { |c| n % c == 0 }
    [f] + factors(n / f)
  end
end

(The other methods stay the same.) With that change, the whole program factors 600851475143 in a few ms (not counting Ruby process startup time).

Why was that change so effective? It's not only that factors was slow; the original program spent about 75% of its time in prime?. But while the original version of factors returned all of a number's factors, both prime and nonprime, the new version of factors only returns primes. (This is because it accumulates the smallest remaining factor, and the smallest prime factor is always smaller than the smallest nonprime factor.) So not only are we now factoring faster, we also have less factors to test for primeness, and the factors we are testing for primeness are smaller and take less time to test for primeness.

What's more, since factors now returns primes we don't need to test primeness at all, so let's rename factors to make it clear that it returns primes and eliminate prime?:

def greatest_prime_factor(n)
  prime_factors(n).max
end

def prime_factors(n)
  if n == 1
    []
  else
    f = (2..n).find { |c| n % c == 0 }
    [f] + prime_factors(n / f)
  end
end

As well as being shorter, that's faster yet, factoring 600851475143 in less than 1 ms (again, not counting Ruby process startup time) on my machine.

Answer 3

Regarding your is_prime? method:

1. Ruby conventions suggest you name it prime?, not is_prime?
2. It doesn't correctly handle cases where n is one or less
3. #select will keep iterating after it has found a match; for best performance it should break out of the loop as quickly as possible
4. A quick optimization is to return false for any number that is evenly divisible by two
5. Your loop can start at three and only iterate over odd numbers
6. Your loop only has to iterate up to the square root of n, instead of n

There was a recent, similar discussion here, and I published a much faster prime? method here.