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"

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

  def test_largest_prime_factor2
    ans = 13195.largest_prime_factor
    assert_equal 29, ans

  def test_largest_prime_factor3
    ans = 600851475143.largest_prime_factor
    assert_equal 6857, ans

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
      factor = factor + 1
    return lastFactor


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.