Speeding up prime factorization

Question

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) 

Answer 1

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.

• user2813274: 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

Answer 2

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.