15 Jan 09 Project Euler: Problem 3 in Ruby

It's been a number of years since my last math class, so I had to bust out the pen and paper. I figured that for given number n you can stop checking for factors after n / 2, but I didn't realize till much later (and by "realize", I mean read up on prime numbers) that you can actually stop checking for prime factors at the square root. This saves considerable time when you're dealing with numbers in the quadrabazillions. It's the difference between < 2 seconds and I-did-the-dishes-and-it's-still-running.

On a side note, I don't consider reading up on the subject "cheating". I consider looking up algorithms and other solutions "cheating".

Problem #3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

target = 600_851_475_143
 
def find_highest_prime_factor n
  (Math.sqrt(n).ceil).downto 2 do |i|
    if n % i == 0 && find_highest_prime_factor(i) == 1
      return i
    end
  end
  1
end
 
puts find_highest_prime_factor(target)

As expected, Olathe delivers. Runs roughly 3 times as fast and is easier on the eyes...even though he loaded an external library (cheater!)

 require 'mathn'
num, factor = 317_584_931_803, 0
primes = Prime.new
while num > 1
  factor = primes.next
  num /= factor while (num % factor).zero?
end
 
puts "Largest factor is #{ factor }."

However, if you're going to cheat...cheat big! Posted by mat:

 require 'mathn'
317584931803.prime_division.last[0]

**UPDATE**
The two not-mine solutions use a different number (317584931803. instead of 600851475143) so the solution is different, but the algorithms are correct.

Tags: project euler, ruby