Problem 3: Largest Prime Factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

---

from math import ceil

def largest_pf(n):
    L = [True] * ceil(n**0.5)
    L[0], L[1] = False, False

    for i in range(2, len(L)):
        if L[i]:
            for j in range(i*2, len(L), i):
                L[j] = False

    primes = []
    for i in range(0, len(L)):
        if L[i]:
            primes.append(i)

    facts = []
    check = n
    for i in primes:
        if check % i == 0:
            facts.append(i)
            check //= i
            
    facts.append(check)
        
    print(facts)
    return max(facts)

print(largest_pf(600851475143))

Click to reveal output

[71, 839, 1471, 6857, 1]
6857

---

See problem 3 on projecteuler.net