Could someone walk me line-by line through this prime sieve? I’m attempting to develop my own sieve but most of the faster ones contain syntax that I don’t understand (like the lines i’ve made comments on). Sorry if this is sort of a newbie question — also if you have any links that could help me with sieve writing they’d be greatly appreciated.
def rwh_primes1(n): """ Returns a list of primes < n """ sieve = [True] * (n/2) # What does the '[True]' mean? for i in xrange(3,int(n**0.5)+1,2): if sieve[i/2]: # The same complaint as in line 3, I don't understand the variable 'sieve' sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) # how is sieve used here - it seems to be as a list but i'm unsure return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]] # 'sieve' is confusing me here yet again.
Advertisement
Answer
I’ll put the meaning of each line of code in italics, and add my comments in normal-face text.
sieve = [True] * (n/2)
Declare a new local variable sieve
and initialise it to the value [True] * (n/2)
. What does that expression mean? [True]
is a single-element list containing only the Boolean value True
. Multiplying a list by a number repeats the list, so sieve
is now an n/2
-element list of all-True
values.
for i in xrange(3, int(n**0.5)+1, 2):
Start counting in steps of 2, starting at 3 and ending at sqrt(n). This particular choice of range is an optimisation of the Sieve algorithm: we could count all the way from 1 to n in steps of 1, but that’d be less efficient.
if sieve[i/2]:
Look at the i/2
th element of the sieve
list. If it’s True
, then continue down the if
branch. The author is using i/2
to compensate for the fact that the code is counting in steps of 2. This way you can work with a shorter list and use less memory.
sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
Update every i-th element of sieve
to False
, starting at i*i/2. sieve[i*i/2::i]
is called slice notation – because it appears on the left-hand side of an assignment this code will update that slice of sieve
. The right-hand side is a repeat of the list-times-number trick. It computes an all-False
list of the correct length.
return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]
This code just turns the True
/False
values in sieve
into a list of prime numbers. The calculation is compensating for the fact that sieve
doesn’t contain any even numbers by multiplying each True
value’s index by 2.