# Sieve of Eratosthenes algorithm question (Python Syntax)

So I was reading the Wikipedia article on the Sieve of Eratosthenes and it included a Python implementation:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity_and_implementation

``def eratosthenes_sieve(n):# Create a candidate list within which non-primes will be# marked as None; only candidates below sqrt(n) need be checked.candidates = range(n+1)fin = int(n**0.5)# Loop over the candidates, marking out each multiple.for i in xrange(2, fin+1):if not candidates[i]:continuecandidates[2*i::i] = [None] * (n//i - 1)# Filter out non-primes and return the list.return [i for i in candidates[2:] if i]``

It looks like a very simple and elegant implementation. I've seen other implementations, even in Python, and I understand how the Sieve works. But the particular way this implementation works, I"m getting a little confused. Seems whoever was writing that page was pretty clever.

I get that its iterating through the list, finding primes, and then marking multiples of primes as non-prime.

But what does this line do exactly:

``candidates[2*i::i] = [None] * (n//i - 1)``

I've figured out that its slicing candidates from 2*i to the end, iterating by i, so that means all multiples of i, start at 2*i, then go to 3*i, then go to 4*i till you finish the list.

But what does `[None] * (n//i - 1)` mean? Why not just set it to False?

Thanks. Kind of a specific question with a single answer, but I think this is the place to ask it. I would sure appreciate a clear explanation.

`L * N` creates and concatenates `N` (shallow) copies of `L`, so `[None] * (n//i - 1)` gives a list of `ceil(n / i)` times `None`. Slice assignment (`L[start:end:step] = new_L`) overwrites the items of the list the slice touches with the items of `new_L`.

You are right, one could set the items to `False` as well - I think this would be preferrable, the author of the code obviously thought `None` would be a better indicator of "crossed out". But `None` works as well, as `bool(None) is False` and `.. if i` is essentially `if bool(i)`.

``````candidates[2*i::i] = [None] * (n//i - 1)
``````

is just a terse way of writing

``````for j in range(2 * i, n, i):
candidates[j] = None
``````

which works by assigning an list of `None`s to a slice of `candidates`.