Project Euler: Problem 3 in Ruby

Problem 3 in Project Euler is as follows:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

I had previously solved this in Groovy/Java. Here is my Ruby solution…

First, the terminology:
Factors are numbers you can multiply together to get another number.
To determine if a number f is a factor of another number n, divide n by f and if the remainder is 0, f is a factor if n.
For example, if n=10 and f=5; 10/5=0, so 5 is indeed factor of 10.
Furthermore, 10/5 leaves a quotient of 2 and a remainder of 0.
Or 30/3 leaves quotient of 10 and a remainder of 0.
Finally, a number is a prime number if it can only be divided by itself and 1.
So 7 is a prime as no number between 1 and 7 is divisible into 7 without leaving a remainder.

OK, next, let’s try a solution. I started by trying a brute force approach along the lines of

• Given a number n (600851475143 in our case), i = step through all numbers between 2 and n.
• If n is divisible by i with no remainder, i is a factor; record it
• Step through the factors in reverse order; If it is a prime, we have found our max Prime

Putting aside how you determine if a number is a prime, this is a poor solution (and took forever to run on my machine).
Stepping through every number up to n is simply too many numbers to consider.
There are small ways to optimize this, for example:

• The max you should be considering is num/2
• We could do things backwards (step through all numbers between n and 2) so that the first prime factor we find must be our solution and we can stop

However, these tweaks still leave it as a very slow solution.

The breakthrough for me was realizing that when we do something like

  limit = num / 2
  i = 2
  while (i < limit )
    if ((num  % i) == 0)
      //i is a factor of num
    end
    i += 1
  end

We are ignoring the fact that although i is a factor of num, the quotient is also a factor of num. For example, if num = 33 and i = 3; the quotient (that is, 11) is also a factor.
And more importantly, if i is the first factor we have found, the quotient is now our new limit; So continuing the previous example, 11 would now become our new limit (rather than 16 which was our initial limit achieved by dividing 33 by 2 and rounding down).
Using this approach, not only can we find 2 factors at a time, we also drastically reduce our search space each time.

I immediately check each quotient to see if it is a factor, since it is the largest possible factor we have found so far. Hence if it is a prime, we can stop our search.
However, we also record the divisor so that we can iterate through those in reverse later, if none of the quotients turn out to be prime factors.

This results in an algorithm like this:

  num = 600851475143
  limit = num / 2
  possibleFactor = 2
  factors = []
  maxFactorFound = false
  while (possibleFactor < limit && !maxFactorFound)
    if ((num  % possibleFactor) == 0)
      quotient = num / possibleFactor;
      if (isPrime(quotient))
        maxFactor = quotient;
        maxFactorFound = true;
      end
      factors.push possibleFactor
      limit = quotient
    end
    possibleFactor += 1
  end
  if (!maxFactorFound)
    factors = factors.reverse
    factors.each { |factor|
      if (isPrime(factor))
        maxFactor = factor
        break
      end
    }
  end
  puts "Max factor for #{num} is #{maxFactor}"

This algorithm took 0.2s on my machine, well below the 1 second limit.
Finally, my approach for determining if a number is a prime is as follows. I’m not sure if this is the most performant approach, but it works:

def isPrime candidate
  for i in 2..candidate/2
    isPrimeFactor = true
    if (candidate%i == 0)
      isPrimeFactor = false
      break;
    end
  end
  return isPrimeFactor
end

Tags: euler, ruby