Shaun Abram
Technology and Leadership Blog
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