Apr 8 2009

Project Euler Problem 3 Solution

by Ash • Project Euler • Tags: Project Euler, Ruby 0 Comments

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

What is the largest prime factor of the number 600851475143 ?

My solution in Ruby:

def is_prime ( p )
  if p == 2
    return true
  elsif p <= 1 || p % 2 == 0
    return false
  else
    (3 .. Math.sqrt(p)).step(2) do |i|
      if p % i == 0
        return false
      end
    end
    return true
  end
end
 
i, num = 1, 1
loop do
  i += 1
  if 600851475143 % i == 0
    num = 600851475143 / i
    break if is_prime(num)
  end
end
 
puts "largest prime factor: " + num.to_s