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.

Answer 2

Finding the largest prime factor of a number really isn't as difficult as people make it out to be.

from itertools import takewhile
from math import floor, sqrt

def _prime_numbers_helper():
    yield 2
    yield 3
    i = 1
    while True:
        yield 6 * i - 1
        yield 6 * i + 1
        i += 1

def prime_numbers(ceiling=None):
    if ceiling is None:
        yield from _prime_numbers_helper()
    else:
        yield from takewhile(lambda number: number <= ceiling, _prime_numbers_helper())

def largest_prime_factor(number):
    if number % int(number) != 0:
        raise ValueError('The number must be an integer.')
    if number in (0, 1):
        raise ValueError('There is no largest prime factor of {}.'.format(number))

    while True:
        for i in prime_numbers(floor(sqrt(abs(number)))):
            if number % i == 0:
                number //= i
                break
        else:
            return number

The else statement only executes when the for statement executes to completion (i.e. when the number cannot be factored any further).

The for statement should be using a true prime number generator instead, but I'm too lazy to write an efficient implementation of it.

Note that this assumes that you are using Python 3.3 or later.

Out of curiosity is this for Project Euler Problem 3?