Home — Project Euler

Let \(p_i = {2, 3, 4, 5, \dots}\) we continue to divide \(c\) by \(p_i\). If \(c\) becomes 1 then \(p_i\) is the greatest prime factor, otherwise we increase \(p_i\) by one. We know that any \(p_i\) that divides \(c\) is prime, because otherwise it would be of the form \(p_i = {q_1}^{a_i} \dotsm {q_n}^{a_n}\) and since \(q_i\) is smaller than \(p_i\), \(c\) would have been already divided by it, so \(p_i\) must be a prime number.

c = 600851475143
p = 2
while c > 1:
    if c % p == 0:
        c /= p
        continue
    p += 1
p

6857