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