How does a Sieve of Eratosthenes work in this code?-CodePudding

I need some help explaining the Sieve of Eratosthenes below. I copied it from some other Stackoverflow page, but I do not understand it line by line. Can someone explain this?

def eratosthenes(n):
    multiples = []
    for i in range(2, n):
        if i not in multiples: 
            print (i)
            for j in range(i*i, n, i):  #Troubled Part
                multiples.append(j)

eratosthenes(100)

I especially do not get the range(i*i...) part. Why are there three attributes in one set of parentheses? Also, why is i squared? Thanks!

CodePudding user response：

Let's go line by line:

multiples = [] makes a list of composite numbers, we'll add here later

for i in range (2,n) we're looping from 2 to n, trying to get all of the primes.

if i not in multiples we're checking if i is a composite number that we've already found

print(i) Well i must be prime, so let's print it out

for j in range(i*i,n,i) Count by is, from i*i to n, as each of these numbers will be a composite number. Note that we're going from i*i, as numbers like i*[number<i] will have been recorded from previous iterations

multiples.append(j) add j to the list of the composite numbers

CodePudding user response：

The third attribute in the range is just an increment. It is saying add i to i*i until we reach n.

So the Sieve of Eratosthenes works by getting rid of multiples of primes (i.e. composites, which are tracked in the multiples list) as we go forward, so like [2,4,6,8,...], [3,9,12,...],[5,25,30,...] as we go on.

In the first of each of the above sequences, we have the prime number, the subsequent elements in the sequence are added to the multiples list

The part where you've highlighted:

for j in range(i*i, n, i):  #Troubled Part
                multiples.append(j)

This is just adding all the composite multiples of the prime numbers. To be more explicit, let's look at 2.

2 is not in multiples. So it is printed. Then let's think concretely about what happens next:

for j in range(2*2, 100, 2)

This will add 4, 6, 8, 10, and so forth to the multiples list, which are the numbers we ignore because they are composites. You can think of i*i as simply the next element in the sequence of multiples that we start at.

In this way, we continue for 3, starting from 9, 12, 15, and so forth.

Notice that the composite numbers 4,6,8 had already been excluded in the first iteration, so that is why we can start at 9 and continue.

This is in fact a significant point that Ryan Fu has pointed out.

So to put this in the clearest terms:

2 is printed. The multiple list is updated with all other even numbers [4,6,8,10,...]
We go to 3 next because it is not in multiples. We add [9,12,15,18,21,...] to the list.
Notice that we do not need to bother adding 6 to the list because it was already previously added when we considered 2. This is why we do not need to do something like

for j in range(i*2, n, i)

The process continues, the next number we have is 5, so [25,30,35,40,...] are added to multiples

Eventually only the primes are printed.

CodePudding user response：

multiples is storing all the multiple of a prime no for eg for 2 is prime no then 4,6,8,10,12... are multiple of and not primes and there is no need to check these no as they are prime or not at we know that they are not.

if i not in multiple indicate that i is prime number, and then we are saving all the multiple of i. in your solution i think there is no need to use i*i in for j in range(i*i, n , i) but 2*i would be right choice ie for j in range(2*i, n, i) and multiples should be of type set not list as this would allow duplicates and search time complexity would be O(N) in list case and O(1) in set case.

def eratosthenes(n):
    multiples = set()
    for i in range(2, n):
        if i not in multiples: 
            print (i)
            for j in range(2*i, n, i):  #Troubled Part
                multiples.add(j)

eratosthenes(100)