3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

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

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.