1
\$\begingroup\$

I have written the following code for returning the list of prime factors. Any speed-enhancing suggestions?

import math
def is_prime(num):
    for n in range(2,math.floor(math.sqrt(num)+1)):
        if num%n==0:
            return False
    return True         

def find_prime_factors(num):
    primes=[]
    for n in range(2,math.floor(num/2)+2):#The maximum value of the factor could only be half of the number
        if is_prime(num):
            primes.append(math.floor(num))
            break
        if is_prime(n) and num %n==0:
            num=num/n
            primes.append(n)
            while num%n ==0:
                num=num/n
                primes.append(n)

    return(primes)      
\$\endgroup\$
2
\$\begingroup\$

Correctness

1 is not a prime factor:

>>> find_prime_factors(25)
[5, 5, 1]

Performance

Primality testing is expensive. You call is_prime() twice on every iteration of the main loop of find_prime_factors(). Furthermore, is_prime() performs trial division in much the same way that find_prime_factors() does, resulting in redundant work.

\$\endgroup\$
  • 2
    \$\begingroup\$ Performance: math.floor(num/2)+2 should be replaced by the sqrt of the number, and upon a match, check for primes with the complement* of the result (i.e. if you have 25, you only need to check up to the sqrt of it, or 5, to find a match - similarly if you were to check 35, you only need to check up to 6, where you would find 5, and then get 7 due to it being the complement* because 35 / 5 = 7, and you would check 7 for primes *complement may not be the correct math term to use \$\endgroup\$ – user2813274 Jul 29 '14 at 16:06
0
\$\begingroup\$

Consider a number num which is the product of two large prime numbers. Say num = 127 x 127. You have a loop with n = 2, 3, 4, 5, 6, ... and every single time through the loop you check whether 127 x 127 is a prime number. And every time you find it isn't. That's very, very inefficient.

Next, you check each number n = 2, 3, 4, 5, 6, ... to see if it is a prime number. Here's a trick: The smallest factor n ≥ 2 of a number must be a prime number. Because if it wasn't a prime number, say n = p*q, then p and q would be smaller factors of n. Therefore n wouldn't be the smallest factor. That's a contradiction, so the assumption that n might not be a prime number must be false. So you don't need the test that n is a prime number at all.

As others said, you need to watch for the case that the highest prime factor is a square or cube etc. like the example 25, where you are left with a factor of 1. Which is not a prime factor but must be completely ignored.

And a trick that makes checking for potential divisiors twice as fast: The only even prime number is n = 2. So check first if num is divisible by 2, then check the numbers n = 3, 5, 7, 9, 11 etc.

And another trick: 3 is the only prime number that is a multiple of 3. So divide by 2 and 3 first, then check the numbers n = 5, 7, 11, 13, 17, 19, 23, 25. How do you create this sequence? You start with n = 5, then add alternatively 2 and 4 to skip the numbers 9, 15, 21 which are all multiples of 3. To do this, you start with n = 5 and add = 2. Then you set n = n + add and add = 6 - add. This alternates add = 2, 4, 2, 4, 2, 4 etc. as you needed.

\$\endgroup\$

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.