当前位置: 动力学知识库 > 问答 > 编程问答 >

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

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

分享给朋友:
您可能感兴趣的文章:
随机阅读: