[Tutor] Prime Factorization Tool

[Steven D'Aprano]

Robert Sjoblom wrote:

> from math import sqrt
> 
> def isprime(n, factor):
>     if n == 1:
>         return False
>     for x in range(2, round(sqrt(n))):
>         if n % x == 0:
>             return False
>     else:
>         return True

factor is not used in the isprime function; get rid of it.

A bug in your code: the stop value in the call to range is sometimes off by 
one. That means that you sometimes wrongly pick a composite number as prime. 
E.g. isprime(25) returns True, but 25 is 5*5 and therefore not prime.

Remember that the "stop" value of the range function is not included in the range:

range(2, 5) => [2, 3, 4]

and so 5 is not tested. You need to include the sqrt. So you need to add 1 to 
the stop to ensure the sqrt is included:

range(2, round(sqrt(n))+1)

But this leads to a trivial inefficiency: sometimes you test one extra number. 
There's no need to round the square root up to the nearest value, e.g. square 
root of 115 is 10.723805294763608 which rounds up to 11. But there's no point 
in testing 11, since 11*11 = 121 > 115 and so 11 can't be a factor (assuming 
you have been reducing the number each time you find a smaller factor). 
Instead of using round, just use int(sqrt(n)) to drop the fractional part.

range(2, int(sqrt(n))+1)

A much more important inefficiency: you don't need to test by even numbers 
except for 2. If a number is divisible by 4, then it is also divisible by 2, 
and so even numbers will always be detected by the "divide by 2" step. Testing 
by dividing by 4, 6, 8, ... is pointless.

So you can roughly double the speed of your function by skipping even numbers 
other than two. Remember that 2 itself is prime, but any other multiple of 2 
is not. Take that test outside of the loop, and then loop over every second 
number starting with 3.

Hint: the range function takes a step size:

range(3, 25, 7) => [3, 10, 17, 24]


-- 
Steven