问题描述:

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.

`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`

.

您可能感兴趣的文章：

- asp.net c# google api Documents - 401 Unauthorized
- javascript - Json only web application. What are the cons? (or Pros)
- Remove HTML using PHP (ob_start + dom parser)
- How I can limit result in SQL Server?
- android - Toast not show in OnItemCLick
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**