
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
.
Finding the largest prime factor
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 thewhile
loop terminates. The conditional of thewhile
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≤1012 and runs test cases up to 10 consecutive trials. This algorithm handles those test cases in less than a tenth of a second.
Project Euler 3 Solution
Runs < 0.001 seconds in Python 2.7.
Afterthoughts
- Trial division, used here, works well for smaller numbers less than 1021, 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
Discussion
No comments yet.