Project Euler: Problem #3
Here’s problem 3:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Here’s my solution:
``` ruby Problem #3 require ‘prime’
primes = Prime.prime_division(600851475143) puts primes.last[0]
#Answer is 6857
The solution was made pretty succint by a powerful Ruby method called <code>prime_division</code>.This method returns the prime factorization of the integer argument as a two dimensional array. To find the largest prime factor of <code>60085147514</code> we just need the last element of the array, but since we're dealing with a two dimensional array, two values would be returned. To mitigate this, just select the first element of the last element of the array with<code>primes.last[0]</code> Here's a more visual explanation:
```ruby
primes.last
>> [6857, 1]
primes.last[0]
>> 6857
Comparison
Solution from eulerlue
on the forums:
```ruby eulerlue’s solution
num = 600851475143
@factors = [2] #skip 1
def get_factors(num) (@factors[-1]..num).each do |i| if num % i == 0 @factors « i get_factors(num/@factors[-1]) return end end end get_factors(num)
#check if the discovered factors are prime prime = [] @factors.each do |num| @factors = [2] get_factors(num) prime « num if @factors.size > 2 #itself and 1 end.max #return greatest
Before benchmarking, I guessed that it would be slower due to the fact that it finds all the factors, then iterates through each one to check whether they are prime or not. Here's the speed comparison:
```plain Speed comparison
# My solution
0.000000 0.000000 0.000000 ( 0.000870)
# Other Solution
0.000000 0.000000 0.000000 ( 0.002585)
Besides the speed decrease with the second solution, it’s harder to read and has a lot more code.