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

The question asks that if the the number 600851475143 was factored into its distinct prime factors, report the largest one found.

This can be done without the use of arrays or a giant list of prime numbers. Instead, we generate prospective prime numbers, p, through sieving. The list of candidates for p are the set of odd natural numbers {2, 3, 5, 7, 9, 11, 13, 15, …}.

The remainder, after removing all other prime factors, p, is the largest prime factor and we can terminate the loop when the current candidate’s square exceeds the residual value of n.

p = 2
while (p*p <= n):      
  if (n % p == 0): 
    n //= p
  else: 
    p += 2 if p>2 else 1   # after 2, consider only odd p

Here's a trace of this algorithm to demonstrate the process of removing prime factors from 
the number n and leaving the largest prime factor p.
n=495
 p      p2   n
p=2 and 4 ≤ 495: 2 is not a factor so its skipped and p is incremented to 3
p=3 and 9 ≤ 495: 3 is a factor: n = 165
p=3 and 9 ≤ 165: 3 is a factor: n = 55
p=3 and 9 ≤ 55: 3 is not a factor so its skipped and p is incremented to 5
p=5 and 25 ≤ 55: 5 is a factor: n = 11
p=5 and 25 ≤ 55: 5 is not a factor so its skipped and p is incremented to 7
p=7 and 49 ≤ 55: 7 is not a factor so its skipped and p is incremented to 9
p=9 and 81 not ≤ 55: p is incremented to 11 and the while loop terminates.
The conditional of the while loop is checked after the loop's last statement.

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. Here’s a Javascript prime factor calculator to find all the prime factors of a number.

The HackerRank version ups the limit for n≤10¹² and runs test cases up to 10 consecutive trials. This algorithm handles those test cases in less than a tenth of a second.

This program and method
solves all test cases for
Project Euler 3 on HackerRank

Project Euler 3 Solution

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 factor: 99990001, <1 sec
  
• n = 600856008514751431475143, iterations:11859442, largest prime factor: 562585074706409, <6 sec
  

Project Euler 3