Project Euler 3: Find the largest prime factor of a composite number

---

Project Euler 3 Problem Description

Project Euler 3: The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Analysis

This can be done without the use of arrays or a giant list of prime numbers. Instead, we generate prospective prime numbers, p, as odd numbers, except for the first one which is 2.

The list of candidates for p are [2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, …]
As you can see many of these are not primes, but that’s OK, because their preceding factors have effectively eliminated them from consideration. For example, 9, 15, 21, … are removed when we divided by 3.

The last prime factor found is the largest and since every composite number has no prime factor greater than its square root we only need to check up to √n.

If the given number, n, is already prime then n is returned as the largest prime factor, which is nice, because it is, in fact, itself the largest prime factor.

Project Euler 3 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 3 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.

Afterthoughts

• Trial division, used here, works well for smaller numbers less than 10²¹, for larger numbers there are several efficient algorithms available.

• A more favorable method for factoring numbers under 100 digits long is the Quadratic sieve, a recent invention. It is a much simpler algorithm to implement compared to others and lends itself to parallelization. Because it is a sieve, large amounts of memory may be required.

• Another is Pollard's Rho algorithm with improvements by Brent. It’s easy to program and fast for numbers with small factors.

• To find the prime factors of any number see: prime factor calculator written in JavaScript.
  

• Some other examples:
  
• n = 600851475143, iterations:738
  
• n = 600851475143600851475143, iterations:5006, largest prime:99990001, <1 sec
  
• n = 600856008514751431475143, iterations:11859442, largest prime:562585074706409, <6 sec