Project Euler Problem 3 – Largest prime factor
The Problem
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
The First Solution
My first instinct when I saw this problem was to see if there was a “Prime” library for Ruby. Indeed, there was. With just a couple lines of code, you can get the answer for this.
require "prime" Prime.prime_division(600851475143)
But I kind of felt that was cheating, so I went and googled how to do prime factorization.
The Test Case
The steps to solve is to keep dividing the number by the lowest prime factor until you reach the largest prime factor. For example, if we were to solve for 75.
- 75 / 3 = 25
- 25 / 5 = 5
- 5 / 5 = 1
class Problem3Test < Minitest::Unit::TestCase def test_largest_prime_factor1 ans = 10.largest_prime_factor assert_equal 5, ans end def test_largest_prime_factor2 ans = 13195.largest_prime_factor assert_equal 29, ans end def test_largest_prime_factor3 ans = 600851475143.largest_prime_factor assert_equal 6857, ans end end
The Solution
The largest prime factor for 75 is 5. In the code, we just increase the factor by 1 in each iteration until we’ve tested every possible factor up to the number. For each factor, we keep dividing by the factor until it is no longer divisible. (In the example, we divide by 5 twice).
class Fixnum def largest_prime_factor n = self factor = 2 lastFactor = 1 while n > 1 if n % factor == 0 lastFactor = factor n = n / factor while n % factor == 0 n = n / factor end end factor = factor + 1 end return lastFactor end end
Notes
In the example above, I used an interesting feature of Ruby where I “open” the Fixnum class and add a new method to it. Now all Fixnum instances will have the largest_prime_factor method.