CODEWITHSUNDEEP
pythonprimessieve-algorithm
Robbie Barrat
Robbie Barrat

Reputation: 520

Failure to understand some prime sieve syntax

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.

Upvotes: 0

Views: 123

Answers (2)

Benjamin Hodgson
Benjamin Hodgson

Reputation: 44634

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/2th 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.

Upvotes: 4

ChrisGuest
ChrisGuest

Reputation: 3608

Assume n=7:

    sieve = [True] * (n/2) # What does the '[True]' mean?

Make a list of boolean True values of length half of n. Eg, sieve = [True,True,True] (as 3.5 was a fraction length it would rounded down in python2)

So xrange(3,int(n**0.5)+1,2) will be a generator that gives us this sequence: []

    for i in 
        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.

When we see [i::2] or somesuch that just meeans we slice the list at recurring intervals. So if mylist contains (0..19):

>>> mylist = range(20)
>>> mylist[0::1]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> mylist[0::2]
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
>>> mylist[0::3]
[0, 3, 6, 9, 12, 15, 18]

Try playing with this yourself so that you are familiar with it. So in this case sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) will be setting every ith value in a list to False.

Upvotes: 1

Related Questions