Question

Here is my code for 1a. What do you guys think? Could it be more efficient?
http://dpaste.com/hold/534504/

Answer 1

in your algorithm you don't have to go all the way up to the candidate number. You can go to (n/2)+1 to cut down on computation

Answer 2

consider divisors up to (n/2)+1 should speed it up

Answer 3

you only need to go to sqrt(n)
careful - optimizing early to the dark side leads
kepp this under your pillow:
http://wiki.python.org/moin/PythonSpeed/PerformanceTips

Answer 4

How come the divisors only need to go up to (n/2)+1?

Answer 5

If there is a divisor bigger than n/2 + 1 how many times would it go into the candidate number? Less than 2 (i.e. 1) which means the divisor is the candidate number itself.

The logic for only going up to sqrt(n) is that if a number has any factors then at least one of them must be bigger than sqrt(n). Think about trying to factorise n as x*y where both x and y are less than sqrt(n). Say you were testing the number 12, you would never get as far as finding that 6 or 4 were factors but that doesn't matter becuase you would have found 2 (12/6) and 3 (12/4) before getting up to the square root. Worst case would be a number that is the square of a prime e.g. 25 where you won't find any factors until you reach the square root.