#### 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

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.

## No comments:

Post a Comment