Calculate highest prime factor very slow

Question

Sometimes when I write a Python 3.x script with too many nested loops and some big values it just takes too long to give the answer. How can I optimize my code so that it runs faster, or where should I optimize?

def isprime(n):
    '''check if integer n is a prime'''
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        return False
    # 2 is the only even prime number
    if n == 2: 
        return True    
    # all other even numbers are not primes
    if not n & 1: 
        return False
    # range starts with 3 and only needs to go up the squareroot of n
    # for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True



ans=0
for i in range(600851475143,0,-1):
if 600851475143%i==0:
    if isprime(i)==True:
        ans=i
        break;
    else:
        continue;
print(ans)

This program should calculate the highest prime factor of the number 600851475143, but it didn't give any answer for half an hour.

Answer 1

You want to compute the largest prime factor of a given number, but it is actually more efficient to look for the smallest prime factors first (and I am just repeating my arguments from my answer). If you test the possible factors in increasing order and divide the given number by a found factor as much as possible, then each found factor is necessarily a prime number. This means that no primality test is needed at all.

This leads to the following function (which is just a translation of the referenced answer to Python):

def max_prime_factor(n):
    '''find the largest prime factor of integer n'''

    largest_factor = 1
    i = 2

    # i is a possible *smallest* factor of the (remaining) number n.
    # If i * i > n then n is either 1 or a prime number.
    while i * i <= n:
        if n % i == 0:
            largest_factor = i
            # Divide by the highest possible power of the found factor:
            while n % i == 0:
                n //= i
        i = 3 if i == 2 else i + 2

    if n > 1:
        # n is a prime number and therefore the largest prime factor of the 
        # original number.
        largest_factor = n

    return largest_factor

Timing for the largest prime factor of 600851475143 (on a 3,5 GHz Intel Core i5 iMac):

• Your method: 43 seconds
• Sieve method from @wei2912: 0.2 seconds
• Above method: 0.016 seconds

Answer 2

I don't think the problem here is having nested loops (you don't have any) but simply the fact that % is an expensive operation and you are performing it 600851475143 times. The runtime for your program appears to be O(n), it is just a very large n.

Also, think about what you are doing. If you are trying to find the largest prime factor, why search all the way up to 600851475143? Any number larger than 1/2 of 600851475143 is not going to be a factor. You are doing more than twice the amount of operations you need to.

Answer 3

Note: The code wasn't properly indented at the time when I started writing this. I've done this for k4droid3 in my answer.

Let's clean up your code before we take a look at why it's slow.

def isprime(n):
    '''check if integer n is a prime'''
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        return False
    # 2 is the only even prime number
    if n == 2: 
        return True    
    # all other even numbers are not primes
    if not n & 1: 
        return False
    # range starts with 3 and only needs to go up the squareroot of n
    # for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

You've used quite a few comments in your code. That's a good start, but remember that comments should explain how things work, not describe what happens. Some of your comments do just that, while others don't. Also, your code could benefit from adding a couple of little functions and space between operators.

And, an important point: iseven() isn't necessary, the interpreter should optimize n % 2 == 0 to n & 1 anyways.

Here's my cleaned-up version:

def isprime(n):
    '''check if integer n is a prime'''
    n = abs(int(n))
    if n < 2:
        return False
    # range starts with 2 and only needs to go up the square root of n
    for x in range(2, int(n ** 0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

As for your second part:

ans=0
for i in range(600851475143,0,-1):
    if 600851475143%i==0:
        if isprime(i)==True:
            ans=i
            break;
        else:
            continue;
print(ans)

It's cleaned up to:

ans = 0
for i in range(600851475143, 0, -1):
    if 600851475143 % i == 0:
        if isprime(i) == True:
            ans = i
            break
        else:
            continue
print(ans)

We can abstract this into a new function to get:

def max_prime_factor(n):
    '''find the largest prime factor of integer n'''
    for i in range(n, 0, -1):
       if n % i == 0:
            if isprime(i) == True:
                return i

print(max_prime_factor(600851475143))

You have two parts in your code. The first one is the checking of prime numbers. The second part is searching for the largest prime factor. I will address the second part as it is simpler to fix that.

You're searching for the largest factor to the number. As DharmaCollective's answer points out, any number larger than the 1/2 of your number is not a factor. However, since you're only searching for prime factors, you can start from the square root of the number. With that, we can cut down the iterations massively:

def max_prime_factor(n):
    '''find the largest prime factor of integer n'''
    for i in range(int(n ** 0.5), 0, -1):
       if n % i == 0:
            if isprime(i) == True:
                return i

And flattening the branches + removing the redundant check for equality with True:

def max_prime_factor(n):
    '''find the largest prime factor of integer n'''
    for i in range(int(n ** 0.5), 0, -1):
       if n % i == 0 and isprime(i):
            return i

After this, I gave the program a run and it gave the following prime factor almost instantly (!!!):

6857

Can we do better?

isprime() is a trial division. For every number, you check for all numbers below the square root of it (excluding <= 2). Because of that, we're going to iterate about $$\sqrt{600851475143} / 2$$ which is about 387573 times.

But there're better ways. We can use the Sieve of Eratosthenes to do a better job. For more information, take a look at How to implement an efficient infinite generator of prime numbers in Python?, which gives a rather efficient (both in terms of memory and time) implementation of the sieve.

Here's the final code:

def postponed_sieve():                   # postponed sieve, by Will Ness      
    yield 2; yield 3; yield 5; yield 7;  # original code David Eppstein, 
    sieve = {}                           #            ActiveState Recipe 2002
    ps = (p for p in postponed_sieve())  # a separate Primes Supply:
    p = next(ps) and next(ps)            # (3) a Prime to add to dict
    q = p*p                              # (9) when its sQuare is 
    c = 9                                # the next Candidate
    while True:
        if c not in sieve:            # not a multiple of any prime seen so far:
            if c < q:                 #   a prime, 
                yield c ; c += 2 ;    #
                continue              #            or
            else:   # (c==q):         #   the next prime's square:
                s=2*p                 #     (9+6,6 : 15,21,27,33,...)
                p=next(ps)            #     (5)
                q=p*p                 #     (25)
        else:                         # 'c' is a composite:
            s = sieve.pop(c)          #   step of increment
        c2 = c+s                      #   next multiple, same step
        while c2 in sieve: c2 += s    #   no multiple keys in sieve (dict):
        sieve[c2] = s                 #         (increment by the given step)
        c += 2                        # next odd candidate

def isprime(n):
    '''check if integer n is a prime'''
    n = abs(int(n))
    if n < 2:
        return False

    for i in postponed_sieve():
        if i >= n:
            return i == n

def max_prime_factor(n):
    '''find the largest prime factor of integer n'''
    for i in range(int(n ** 0.5), 0, -1):
        if n % i == 0 and isprime(i):
            return i

print(max_prime_factor(239836885100623))

postponed_sieve is a generator that returns an infinite list of primes. In isprime, I've set up a for loop that keeps on yielding values from postponed_sieve till the prime exceeds or is equal to n. Afterwards, I terminate the loop by returning i == n.

Time for an informal benchmark. I've computed the multiple of 2 primes, 15485867 and 15487469, and it returned the larger of the 2 after a few seconds:

wei2912@localhost ~/tmp> python isprime.py
15485867

I think this is about the fastest we can go. :)

EDIT: It's late at night and I screwed up the code. There can be a prime factor greater than the square root of the integer. Go by dividing the number by half. The rest of the answer still applies. Unfortunately, I'm on my phone right now so I can't change the code.

EDIT 2: Changing to division by half slows down the program by a huge magnitude (and will render this answer useless). There's a way to salvage this, which is to search from bottom up, then divide by the smallest prime factor and continue. Martin R's answer addresses this well; please take a look at that answer instead.