# Factorisation code running slow

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) == :  # if prime factors
prime_factors.append(factor)
return prime_factors


• 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) == ), 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.

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.

• In the code that you describe, what's i? – Pimgd Feb 13 '15 at 14:01
• Sorry, cut & paste error. Now it should be clearer. – NicolaSysnet Feb 17 '15 at 10:14