Prime factoring problem

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


I complicated this problem by trying to list all the primes below the square root of 600851475143 using  Sieve of Eratosthenes algorithm. However this problem can actually be solved by a very simple way:

1. Find the smallest prime factor 'spf ' of n
2. Let n be the quotient of the division n  / spf
3. Repeat step 1 and 2 until n is equal to 1

The trick is to find the smallest prime factor of n in every iteration. However, this issue can be tackled easily by starting with '2' as the divisor and continuing with successive numbers (can be even optimized without going through all the successive numbers). Whenever you hit a divisor that can divide n, it is a prime, and of course, also a factor.

In other words, this trick exploits the fact that smallest factor of a number must be a prime. Think about it for a moment!

My program solved this problem gracefully and gave the answer: 6857