2

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]:
            continue

        candidates[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.

sarnold
  • 102,305
  • 22
  • 181
  • 238
SpacePrez
  • 1,086
  • 7
  • 15
  • 2
    To see how far a pure Python implementation of Sieve of Eratosthenes can go look at answers by @Robert William Hanks http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python http://stackoverflow.com/questions/2897297/speed-up-bitstring-bit-operations-in-python – jfs Apr 10 '11 at 12:28

2 Answers2

3
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 Nones to a slice of candidates.

dan04
  • 87,747
  • 23
  • 163
  • 198
2

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).

  • I get the None and the if i, but what I'm wondering is, whats the real difference between = None and = [None] * (n//i -1) Why make the copies of None? Are you setting multiple numbers to false in a row? I suppose you're replacing the slice all at once with a new list which is made up of multiple [none] entries... would = None compile or be a syntax error? (assigning each individually like with false instead of replacing the set with a set) Hm gotta try this... – SpacePrez Apr 11 '11 at 03:06
  • 1
    @Zaphod: Using the slice `[::2]` of `range(10)` for simplicity, `xs[::2] = None` raises `TypeError: must assign iterable to extended slice` while `xs[::2] = [None] * 6` works as expected. So yeah, simply `None` won't work. –  Apr 11 '11 at 16:30