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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s