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
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
