WAP to Find The Largest Prime Factor Number

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?


The solution to this problem is simple. But the main problem here is to construct a rock solid method that returns whether a given number is prime or not. A prime number is a number which divisible by itself and 1 only. Example of prime numbers are 2,3,11,4999. The following is the ruby code to find whether or not a number is prime or not. You may see that I have used a square root of the number as the upper bound, the simple reason being, there cannot be a number greater than the square root of that number being prime (you can get it if you think deep)

def is_prime(n)
return false if n <= 1
2.upto(Math.sqrt(n).to_i) do |x|
return false if n%x == 0
end
true
end

Now that we have written a method that returns whether or not a number is prime, the rest of the problem is fairly simple. Again, we have to use the square root property. It is enough if we run the prime number validation from the square root of the number. We will have to traverse all the way to 2 for this. The first occurring prime factor is ofcourse the solution to our problem.

Math.sqrt(600851475143).to_i.downto(2) do |n|
if is_prime(n) && 600851475143%n ==0
puts "Maximum prime factor for this number is #{n}"
break
end
end