Hello,
I am a newbie to python. I am trying to practice writing a code in
python and am trying to write a function to generate prime numbers
using sieve of Eratosthenes. (code follows at the end of mail)
The way it is coded, if I change the for loop over "j" from
for j in range( (2*i*(i + 1)), np, (2*i +1)):
to
for j in range( (2*i*(i + 1)), np, 2*(2*i +1)):
I should get the same output for the two (which I do).
The second for loop has to make roughly half the iterations compared
to the first, because I increased the step-size by factor 2.
However when I time the code for the two different for loops, I
observe that the code takes longer to run as compared the first for
loop.
This seems to be counter intuitive. Can someone explain this behavior ?
Also if I replace the for loop by while loop, it takes longer to run,
which I guess could be because in case of for loop it kind of knows
how many iterations to make, but in while loop it has to keep checking
every time.
Thank you,
Yash
<code>
def primes(Nmax):
""" primes(Nmax) -> list of prime numbers between 1 to Nmax
Generates a list of primes numbers between 1 and Nmax, including Nmax,
using Sieve of Eratosthenes.
"""
# Author -Yash Kochar
# Last modified -23rd June 2009
#---------------------------------------------------------------------------
# Check input :
try :
Nmax = int(Nmax);
except ValueError :
print('Unable to convert input to integer.');
except TypeError :
print('Input value should be a number or string.');
except :
print('Something unexcepted happen while trying to convert input to '\
'int-type.');
# Set flags for odd prime numbers :
if ( Nmax < 2 ) :
plst = [];
else :
plst = [True]*( (Nmax +1)//2 ); # start with True for [1, 3, 5, 7, ...]
plst[0] = False; # 1 is not prime
np = len(plst); # Number of odd numbers to be considered
for i in range(1, int(((2*np +1) **0.5) +1)):
if plst[i]: # Number is a prime
for j in range( (2*i*(i + 1)), np, (2*i +1)):
plst[j] = False;
# Filter out the required values (all odd primes) :
plst = [(2*n +1) for n in range(0, np) if plst[n]];
plst.insert(0, 2); # Append "2" at the beginning.
return plst;
</code>
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
