5
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review SE! Just to point out, you should indent your code properly (specifically the function isprime), otherwise it won't work in Python. \$\endgroup\$ – wei2912 Nov 18 '14 at 17:19
  • 1
    \$\begingroup\$ I would find the factors starting from the smallest, and dividing my target until I find that one of the factors is bigger than remaining. \$\endgroup\$ – njzk2 Nov 18 '14 at 20:00
  • \$\begingroup\$ Even for i in range(600851475143,0,-1): a = 42 would take a very very very long time to compute. \$\endgroup\$ – Maxime Nov 18 '14 at 20:53
  • 1
    \$\begingroup\$ This is Project Euler Problem 3. \$\endgroup\$ – 200_success Nov 19 '14 at 7:26
  • \$\begingroup\$ Once you find 71 as a factor: 1) You can divide the original number by 71 and only go up to the square root of that. 2) In your new search, you know that there are no factors less than 71. So once you find 71 as a factor, you have at most 91,992 steps left. So if your algorithm needs more than 92,063 steps to factor this number, it's worse than the most obvious algorithm. \$\endgroup\$ – David Schwartz Jul 19 '16 at 3:08
10
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Great job there. I should have figured out that the best way would be to start from the bottom. :) \$\endgroup\$ – wei2912 Nov 19 '14 at 7:10
  • \$\begingroup\$ @wei2912: Thank you for suggesting a cleaner version. But I have rejected the edit because it seems to be incorrect, for example max_prime_factor(4) would return 1. \$\endgroup\$ – Martin R Nov 19 '14 at 7:45
  • \$\begingroup\$ Alright, I'll see if I can fix that. \$\endgroup\$ – wei2912 Nov 19 '14 at 8:04
  • \$\begingroup\$ Okay, I've fixed the problem; the code should be fine now. \$\endgroup\$ – wei2912 Nov 19 '14 at 8:11
  • \$\begingroup\$ @wei2912: Yes, it did work now, but now it works almost identical to my version, and all the explaining comments were removed in your edit. I would prefer to keep my version, but thanks anyway. \$\endgroup\$ – Martin R Nov 19 '14 at 8:16
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It's a bit more than O(n)... But anyway, n is big enough to be an issue even without the call to isprime. \$\endgroup\$ – Maxime Nov 18 '14 at 20:56
  • 3
    \$\begingroup\$ In fact, anything more than the square root of 600851475143 is not going to be a factor, because if it was, it would have a corresponding factor less than the square root. \$\endgroup\$ – Kyle Nov 19 '14 at 3:21
4
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ I am not sure if that is what you meant in your last edit, but 15485867 is a wrong result because the other prime factor 15487469 is larger. \$\endgroup\$ – Martin R Nov 18 '14 at 19:04
  • \$\begingroup\$ Yes, that is the case. The problem is that in my code I've limited the search of the largest prime factor to the square root of the integer, not half of it, resulting in the smaller prime factors being left out. \$\endgroup\$ – wei2912 Nov 19 '14 at 4:57
  • \$\begingroup\$ okay, I will write comments to better describe my program next time! \$\endgroup\$ – k4droid3 Nov 19 '14 at 10:07
  • \$\begingroup\$ instead of "if isprime(i) == True", you can just do "if isprime(i)" Just to make it a bit more pythonic \$\endgroup\$ – usethedeathstar Nov 19 '14 at 12:19
  • \$\begingroup\$ Is that for me or for k4droid3? \$\endgroup\$ – wei2912 Nov 19 '14 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.