Factorisation code running slow

Question

I'm still in the process of learning Python and am doing some of the Project Euler problems.

I have made a factorisation algorithm that works; however, it runs really slowly, and I'm not too well-versed on coding for performance. If someone could give me some pointers on how to improve the algorithm's efficiency it would be a huge help.

def factorise(num_to_factorize):
 """This method returns a list of factors for a particular number passed in to the parameters."""
 factors = []
 for i in range(1,math.floor(num_to_factorize/2)+1): # Loops from 1 to half the number, floors for odd numbers.
 if num_to_factorize % i == 0: # Factor check.
 factors.append(i) # Append on to an array to be checked.
 factors.append(num_to_factorize) # Append the number itself as it is a factor.
 return factors
def prime_factorise(num_to_prime_factorize):
 """This method returns the prime factors of the number passed in to the method as a parameter."""
 prime_factors = []
 for factor in factorise(num_to_prime_factorize): # Loop through each factor.
 if factorise(factor) == [1, factor] or factorise(factor) == [1]: # if prime factors
 prime_factors.append(factor)
 return prime_factors

Answer 1

I'll give you some hints/comments:

• factorise(factor) == [1, factor] or factorise(factor) calculates factorise(factor) twice, consider saving its result as a variable and re-using it instead of incurring the cost twice.
• You're treating 1 as a special case (in factorise(factor) == [1]), but it isn't. 1 can be factored into anything, but should not be considered a prime factor. Why? Because 1 isn't a prime.
• I think your algorithm might be slightly off. For example, if I say prime_factorise(8) I get [1, 2], but I believe the answer should be [2, 2, 2] since 2 is prime, and 2*2*2 = 8.
• Overall, my biggest hint would be try to improve your algorithm by thinking of the operation as a reduction from some number, into its prime factors. Think _how can I transform num_to_prime_factorize into a list of its prime factors ("transform" being key).

I don't want to give away the answer, so, hopefully these tips will suffice to get you in the right direction.

Answer 2

Well... there are so many improvements that I don't know where to start.

I'll give you a first hint: imagine you have to factorise 24, your factorise function will return [1, 2, 3, 4, 8].

You will go on factorising all the elements, just to discover that 4 and 8 are not primes.

To improve this algorithm just forget the factorise function and do everything in prime_factorise:

def prime_factorise(num_to_prime_factorize):
 """This method returns the prime factors of the number passed in to the method as a parameter."""
 prime_factors = []
 for factor in range(1,num_to_factorize/2):
 if num_to_factorize % factor == 0: # Factor check.
 while num_to_factorize % factor == 0:
 num_to_factorize /= factor 
 prime_factors.append(factor)
 return prime_factors

the inner while loop gives you a big hand solving this problem.

Obviously you can further optimise the two loops (google Sieve of Eratosthenes). But this was just a hint.

• Pimgd: In the code that you describe, what's i?
• NicolaSysnet: Sorry, cut & paste error. Now it should be clearer.