CODEWITHSUNDEEP
pythonprimessieve-algorithm
DarkRunner
DarkRunner

Reputation: 449

Understanding Prime Sieve

I'm trying to understand a user's implementation of Erastothene's Prime Seive; the code is only a few lines, but I'm having remarkable difficulty understanding it: 

def eratos_sieve(n):
  sieve = [True] * n
  for i in range(3,int(n**0.5)+1,2):
      if sieve[i]:
          sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
  return len([2] + [i for i in range(3,n,2) if sieve[i]])

My unerstanding thus far is this: We're defining a function with a parameter n. We begin by assuming that n is prime. Then, for some reason, we have a for loop with 3 parameters! And after that if statement, I'm just totally lost. If anyone can help, that would be great!

Upvotes: 0

Views: 166

Answers (1)

cdlane
cdlane

Reputation: 41885

Perhaps my code commentary below might be of help to you -- I also simplified the code where I could (and hopefully didn't break it!):

def eratos_sieve(n):

    ''' Return the number of primes less than n '''

    # Create an array [True, True, True, ...] of length n
    # i.e. assume all numbers are prime unless proven otherwise
    sieve = [True] * n

    # loop over odd numbers from 3 to sqrt(n)
    for i in range(3, int(n**0.5) + 1, 2):

        if sieve[i]:  # if sieve[i] is still True, i is a prime!
            # Assign elements of sieve from i squared to the
            # end of the array skipping by 2 * i (hit multiples
            # of i but skip the even ones) to False. Since this
            # is an array to array assignment, create an array of
            # [False, False, False, ...] of the correct size:
            sieve[i*i::2*i] = [False] * ((n-i * i-1) // (i*2) + 1)

    # Add up odd elements of sieve (True = 1, False = 0),
    # Add one for '2' which we assumed prime:
    return 1 + sum(sieve[3::2])

The code is complicated somewhat in that it's skipping over even numbers, which is fine. A more optimized solution would also reduce the number of elements in sieve by half instead of storing the even elements it's ignoring. This, of course, makes the indexing more complicated, but doable.

Upvotes: 2

Related Questions