Understanding the sieve of Eratosthenes

Question

I am currently going through all of the algorithms we learned about in a certain class, trying to understand what each does and how. However, I am a bit clueless about a certain line in our Eratosthenes sieve:

def sieve(n):
    primes = []                           # list
    is_prime = [False,False]+[True]*(n-1) # how does a list [false,false,true,true....] do anything?
    
    for p in range(2,n+1):                #number from 2 to n
        if is_prime[p]:                   #how does this same list finds out if it is a prime number?
            primes.append(p)              # adds p the list
            for i in range(p**2,n+1,p):   # goes from the square of p to n, in p long steps
                is_prime[i]=False         # those found obviously aren't prime
    
    print(primes)                         # prints the list

This is a really simple algorithm, its base function works on something that I do not understand, so that is a bit of a problem. Someone please explain to me what it does, thank you.

Why don't you try to `print(is_prime)` just after this line and see how it looks? Or just try what `[True]*3` is, for example, and what happens when you add `+` two lists? — Thierry Lathuille, Dec 19 '20 at 16:36
Are you asking about `if is_prime[p]`? It simply looks up the `p`th element in the array `is_prime`. — tripleee, Dec 19 '20 at 16:37
E.g. https://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python should help understand the algorithm, even if the code is slightly different. — tripleee, Dec 19 '20 at 16:40
In case, you have difficulties understanding it, there are many websites and [video tutorials](https://www.youtube.com/embed/ATyAnOCI1Ms?feature=oembed) that explain the algorithm in detail. — Mr. T, Dec 19 '20 at 16:40

score 0 · Accepted Answer · answered Dec 19 '20 at 16:46

So, this sieve works by assuming all numbers to be prime. This is what the is_prime list is for. It's a list which has a boolean (False/True) for every number, and at first, all numbers larger than 1 are considered prime.

As we step through the numbers one by one, we can check if this number has previously been discarded. If it has not, then we add it to the primes and start discarding all multiples of it.

Example: Let's assume we run sieve(6). Then is_primes is initialized as [False, False, True, True, True, True, True]. Note how the index here corresponds with each number. The first two false numbers represent 0 and 1.

In the first iteration, where we check the number 2, we find that is_prime[2] is True. So we add 2 to primes and discard all multiples of 2 so that the list becomes [False, False, True, True, False, True, False].

Arriving at 3, we do the same thing, discarding all multiples of 3 after adding it to the primes list, and at 4 we see that the number has been discarded (is_primes[4] is False), so don't do anything.

This continues ad infinitum.

Understanding the sieve of Eratosthenes

1 Answers1