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.