The prime factors of \(13195\) are \(5, 7, 13\) and \(29\).
What is the largest prime factor of the number \(600851475143\)?
Define a sequence: Let \(n_1 = n\), and for all \(d \geq 2\), let \(n_d\) equal \(n_{d-1}\) divided by the largest power of \(d\) that divides \(n_{d-1}\). For example, if \(n = 450\), then \(\{n_d\} = \{450, 225, 25, 25, 1, 1, 1, \ldots\}\)
If \(d\) divides \(n_{d-1}\) (and hence \(n_{d-1} > n_d\)), then \(d\) is prime. We know this because we've already factored out all powers of smaller numbers, so \(n_{d-1}\) is not divisible by any of \(2, 3, \ldots, d-1\).
The final value of the sequence will be 1. The largest prime factor of \(n\) is therefore the first \(d\) for which \(n_d = 1\).
If \(d^2 > n_d > 1\), then clearly \(n_d\) is not divisible by two prime factors larger than \(d\), so \(n_d\) is prime — and thus the largest prime factor of \(n\). This means we can stop checking values of \(d\) when \(d^2\) goes over \(n_d\), so the worst-case runtime is thus \(O(\sqrt n)\).
def p3(n=600851475143):
d = 1
while n > 1:
d += 1
while n > 1 and n % d == 0:
n //= d
if d ** 2 > n > 1:
return n
return d