Project Euler–Problem 3

Description

From Project Euler:

The prime factors of 13,195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600,851,475,143?

Solution

The solution to this problem actually involves solving another problem that we’ll need later. Namely: computing the prime factors of a number. For this we’ll actual extend the Integer class to include a prime_factors method. This method will return an array that contains all of the prime factors for the current number. The solution will then be to simply find the largest value in the array.

class Integer
 def prime_factors
  prime = 2
  result = []
  value = self
  while value >= prime ** 2
   if value % prime == 0
    result << prime
    value /= prime
   else
    prime += 1
   end
  end
  result << value
 end
end
600_851_475_143.prime_factors.max

There are a number of optimizations that we can eventually make to this method, but we’ll hold off until we actually need the pieces necessary to improve it. One such piece will come in problem five.
The full source and specifications can be seen on github. Next time, finding the largest palindrome made from the product of two 3-digit numbers.