efficient ways of finding the largest prime factor of a number

Question

I'm doing this problem on a site that I found (project Euler), and there is a question that involves finding the largest prime factor of a number. My solution fails at really large numbers so I was wondering how this code could be streamlined?

""" Find the largest prime of a number """


def get_factors(number):
    factors = []
    for integer in range(1, number + 1):
        if number%integer == 0:
            factors.append(integer)
    return factors

def test_prime(number):
    prime = True
    for i in range(1, number + 1):
        if i!=1 and i!=2 and i!=number:
            if number%i == 0:
                prime = False
    return prime

def test_for_primes(lst):
    primes = []
    for i in lst:
        if test_prime(i):
            primes.append(i)
    return primes


################################################### program starts here
def find_largest_prime_factor(i):
    factors = get_factors(i)
    prime_factors = test_for_primes(factors)
    print prime_factors


print find_largest_prime_factor(22)

#this jams my computer
print find_largest_prime_factor(600851475143)

it fails when using large numbers, which is the point of the question I guess. (computer jams, tells me I have run out of memory and asks me which programs I would like to stop).

************************************ thanks for the answer. there was actually a couple bugs in the code in any case. so the fixed version of this (inefficient code) is below.

""" Find the largest prime of a number """


def get_factors(number):
    factors = []
    for integer in xrange(1, number + 1):
        if number%integer == 0:
            factors.append(integer)
    return factors

def test_prime(number):
    prime = True
    if number == 1 or number == 2:
        return prime
    else:
        for i in xrange(2, number):
            if number%i == 0:
                prime = False
    return prime


def test_for_primes(lst):
    primes = []
    for i in lst:
        if test_prime(i):
            primes.append(i)
    return primes


################################################### program starts here
def find_largest_prime_factor(i):
    factors = get_factors(i)
    print factors
    prime_factors = test_for_primes(factors)
    return prime_factors


print find_largest_prime_factor(x)

Answer 1

From your approach you are first generating all divisors of a number n in O(n) then you test which of these divisors is prime in another O(n) number of calls of test_prime (which is exponential anyway).

A better approach is to observe that once you found out a divisor of a number you can repeatedly divide by it to get rid of all of it's factors. Thus, to get the prime factors of, say 830297 you test all small primes (cached) and for each one which divides your number you keep dividing:

• 830297 is divisible by 13 so now you'll test with 830297 / 13 = 63869
• 63869 is still divisible by 13, you are at 4913
• 4913 doesn't divide by 13, next prime is 17 which divides 4913 to get 289
• 289 is still a multiple of 17, you have 17 which is the divisor and stop.

---

For further speed increase, after testing the cached prime numbers below say 100, you'll have to test for prime divisors using your test_prime function (updated according to @Ben's answer) but go on reverse, starting from sqrt. Your number is divisible by 71, the next number will give an sqrt of 91992 which is somewhat close to 6857 which is the largest prime factor.

Answer 2

Here is my favorite simple factoring program for Python:

def factors(n):
    wheel = [1,2,2,4,2,4,2,4,6,2,6]
    w, f, fs = 0, 2, []
    while f*f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f, w = f + wheel[w], w+1
        if w == 11: w = 3
    if n > 1: fs.append(n)
    return fs

The basic algorithm is trial division, using a prime wheel to generate the trial factors. It's not quite as fast as trial division by primes, but there's no need to calculate or store the prime numbers, so it's very convenient.

If you're interested in programming with prime numbers, you might enjoy this essay at my blog.

Answer 3

My solution is in C#. I bet you can translate it into python. I've been test it with random long integer ranging from 1 to 1.000.000.000 and it's doing good. You can try to test the result with online prime calculator Happy coding :)

public static long biggestPrimeFactor(long num) {
    for (int div = 2; div < num; div++) {
        if (num % div == 0) {
            num \= div
            div--;
        }
    }
    return num;
}