Problem 003

Project Euler

Largest prime factor

Problem 3

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

What is the largest prime factor of the number 600851475143 ?

The brute force solution is to test each factor of the number to see if they are prime and output the largest one. However, when looping through all the numbers, the even one can be skip unless the number is 2. In additional, because a \mid n means that b = n / a and I can recursively test both a and b until the largest prime value is found, \sqrt{n} is used as the upper limit for the loop. The complexity is not pretty with this algorithm but modern computer does this in no time. Since the number is much greater than the maximum value for integer type, unsigned long long was used to make sure the number will fit.