Project Euler Problem 3 Statement
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?
Solution
A reasonable way to solve this problem is to use trial division to factor an integer, $n$. In this instance, we create a set of possible integer factors, $d$, from the set $\{2\} \cup \{3, 5, 7, 9, 11, \dots, \sqrt{n}\}$ and try to divide $n$.
For all $d$ that divide $n$, we remove $d$ and all its factors. Once our set of factors are exhausted, the remainder becomes the largest prime factor.
Below is a walk–through of this algorithm to show the process of removing factors and leaving the remainder as the largest prime factor of $n$.
Finding the largest prime factor
n = 6435
d = 2
while (d*d <= n):
if (n % d == 0):
n //= d
else:
d += 2 if d>2 else 1 # after 2, consider only odd d
Example: n = 6435 Step d d2 n n%d==0(d divides n)? 1 2 and 4 ≤ 6435 N: 2 is not a factor of 6435, increment d to 3 2 3 and 9 ≤ 6435 Y: 3 is a factor of 6435: n=n//3 = 2145 3 3 and 9 ≤ 2145 Y: 3 is a factor of 2145: n=n//3 = 715 4 3 and 9 ≤ 715 N: 3 is not a factor of 715, increment d to 5 5 5 and 25 ≤ 715 Y: 5 is a factor of 715: n=n//5 = 143 6 5 and 25 ≤ 143 N: 5 is not a factor of 143, increment d to 7 7 7 and 49 ≤ 143 N: 7 is not a factor of 143, increment d to 9 8 9 and 81 ≤ 143 N: 9 is not a factor of 143, increment d to 11 9 11 and 121 ≤ 143 Y 11 is a factor of 143: n=n//11 = 13 10 11 and 121 > 13: the while loop terminates and 13 is the largest prime factor1 1The while’s conditional, d2 ≤ n, is checked after executing 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.
HackerRank version
HackerRank Project Euler Problem 3 runs 10 test cases to find the largest prime factor of a given number $N$, where $10\le N\le 10^{12}$.
Python Source Code
for _ in range(int(input())):
N = int(input())
while N%2==0: N//= 2
p = 3
while (p*p <= N):
if (N % p == 0):
N //= p
else:
p+= 2
print(2 if N==1 else N) Last Word
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. 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. It’s easy to program and fast for numbers with small factors.
For a practical application of this algorithm see the JavaScript prime factor calculator. It finds all the prime factors of a number.