Question

Hey everyone!

I'm up to lecture 8 and loving it. I set myself my own little assignment. It's a good extension task to problem set 1 if anyone else is interested.

Make a program to list any number as a product of its prime factors.
E.g.
100 = 2x2x5x5
7824 = 2x2x2x2x3x163

I have managed to create the program to but my problem is that my method of finding all the possible prime numbers <= n is inefficient (n being the number that I need to decompose into it's prime factors).

I would appreciate any advice on improving it's efficiency. Thanks.

http://pastebin.com/6PcrCUGf

Answer 1

1. Once you find a divisor, you know the number isn't prime, so you can stop looking.
2. Use [].append() to add an element to a list. The += operator will create a copy of the list for each element you add.
3. You're saving the list of primes less than n, but you're recalculating it for every call to findPrimes. If you called findPrimes(21) then findPrimes(23), you really only need to look for the primes from 22 to 23 (because you've already found the primes up to 21). This isn't as easy a change as the other 2 suggestions, but if you're trying to make it as efficient as you can, this would be a good change to add.

Also, my general admonishment: don't compare boolean variables to True/False. The variable is already the condition.

Answer 2

well done for you!

Answer 3

hey, thanks for the advice dmancine. Point 1 is really helpful. I can't believe I didn't see that. I'm aware I can use the append() module but I wasn't sure it made that much of a difference?

I had thought of doing point 3 but I suppose I was after a way to tackle this problem that wasn't quadratic. It takes a while to calculate all the primes for very large numbers.

Thanks again, I'll implement the changes and see how it goes.