Largest Prime Factor Python

Question

I'm trying to find the largest prime factor of a given number (600851475143) using Python. I've made the following code, but the problem is, it takes forever, probably because it's iterating through lists millions of times. How to optimize this process?

def factors(n):
    list = []
    i = 1
    while i < n:
        if n % i == 0:
            list.append(i)
        i += 1
    return list

def prime(n):
    list = factors(n)
    primelist = []
    for item in list[1:]:
        if item % 2 != 0 and item % 3 != 0 and item % 4 != 0 and item  \
        % 5 != 0 and item % 6 != 0 and item % 7 != 0 and item % 8 != 0 \
        and item % 9 != 0:
            primelist.append(item)
    return primelist

def greatestprime(n):
    list = prime(n)
    list[0] = lnum
    i = 1
    while i < len(list):
        if list[i] > lnum:
            lnum = list[i]
    return lnum

#print(greatestprime(600851475143))

Answer 1

If you are only factorizing a single number n, then the naive approach of testing every number from 2 to sqrt(n) (square root of n) should give result quickly for numbers up to 10¹⁴. You are writing more code than necessary.

Slightly better approaches would be:

• Test 2, then test every odd number
• Test 2, 3, 5, then test all integers of the form 6k + 1 and 6k + 5 where k >= 1
• The 2 approaches above are wheel factorization with n = 2 and n = 2*3 = 6 respectively. You can raise it up to to n = 2*3*5*7 = 210 (higher would not bring much efficiency).

Slightly better approach would be to generate primes via Eratosthenes sieve and test (no redundant test). There are even better approaches such as Pollard's rho factorization, but both methods are overkill unless you are working with more numbers.