Project Euler 3 - Largest Prime Factor

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

What is the largest prime factor of the number 600851475143 ?

Official link:

Thought Process

We need to think of a smart way to get the prime factorization of a number, this is an extremely useful tool that will be used for many problems.

One very quick way goes as follows: continuously remove all the factors of 2 from a number, we then have are left with a smaller number, which we will then remove the factors of 3,4,5 and so on.

The key here is that the number we are checking for does not have to be prime. Why?

Because we are removing the smallest prime factors already, it is impossible that the number will be divisible by 4 because 2 will have removed them all, similarly for 6, we have already checked 2 and 3 so there will be no factor of 6.

This algorithm is efficient because checking whether it is divisible by composite number takes only 1 operation

Interactive Code

Enter a number (yourinput)

Code will output the largest prime factor of yourinput