Databases
StackOverflow2013
Postsdbo
POSieve of Eratosthenes algorithm question (Python Syntax)
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSieve of Eratosthenes algorithm question (Python Syntax)
    text
    copied!<p>So I was reading the Wikipedia article on the Sieve of Eratosthenes and it included a Python implementation: <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity_and_implementation" rel="nofollow">http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity_and_implementation</a></p> <pre><code>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] </code></pre> <p>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.</p> <p>I get that its iterating through the list, finding primes, and then marking multiples of primes as non-prime.</p> <p>But what does this line do exactly:</p> <pre><code>candidates[2*i::i] = [None] * (n//i - 1) </code></pre> <p>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.</p> <p>But what does <code>[None] * (n//i - 1)</code> mean? Why not just set it to False?</p> <p>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.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload