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.

1. 75 / 3 = 25
2. 25 / 5 = 5
3. 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.

https://github.com/travisluong/projecteuler