## Project Euler Problem 3 – Largest prime factor

02.09.2015

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