Finding the Largest Prime Factor in Ruby

Note: This problem is sourced from a popular coding/mathematics website. Chances are you know the one I’m talking about, but I won’t mention it by name because I don’t want give away the answer (as per the site’s policy). That’s not to say I didn’t have to google it myself to get the O(n) down.

The problem: Find the largest prime factor of 600_851_475_143.

We’re going to be using naked Ruby for this one, so no require ‘prime’ or is_prime? magic. Of course, writing your own is_prime? method is the easy part:

def is_prime?(n)     
  tests = Array (2..Math.sqrt(n).floor) 
  tests = tests.select { |x| n % x == 0} 
  return true if tests.empty?
  false 
end

Not that we’re too concerned about it just yet, but this function clocks in at O(n), because it iterates once through an array of length n.

The second part of the problem is also quite simple if we want to find the largest prime factor (LPF) of a smaller number such as, say, 1337:

def largest_prime_factor(n)
 test = 3
 out = 0
 while test <= n
  if ((n % test == 0) && is_prime?(test)) 
   out = test
  end
   test+=1
 end
 return out
end

This returns 191 for 1337, which a quick & easy Google search will tell you is the largest prime factor of 1337. Try passing a number like 600_851_475_143 into the above function, though, and you’ll look like this by the time your computer gives you an answer:

Poor sucker’s coworkers didn’t even notice.

We’re testing every factor to see if it’s prime — basically, iterating through an array, stopping at each value of the array to in turn iterate through it. Each iteration takes O(n) time, so the function as we have it is O of n squared time. That’s less than ideal.

Fortunately, when we find a factor, we can immediately find a larger factor by finding the remainder when our value is divided by that factor. And when we find prime factors of remainders, we actually find prime factors of the number itself. So the simple addition of one line solves all our problems:

n = n/test

Run time, while still being problematic for extremely large numbers, is not a problem at all for 600_851_475_143. This is closer to an O(n) solution. Instead of checking every number between here and yonder, we intelligently divide the number we’re testing by each answer as we find it. We don’t turn into skeletons. We live to see another day.

The code, in it’s final form (sans the above is_prime? method):

def largest_prime_factor(n)
 test = 3
 out = 0
 while test <= n
  if ((n % test == 0) && is_prime?(test)) 
   out = test
   n = n/test
  end
   test+=1
 end
 return out
end