What function sieve is doing?

#1

what function sieve is doing ?

#2

It is used to calculate prime numbers. Add them in a vector and then return the vector. Haven’t you studied Sieve of Eratosthenes?

The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so (Ref Wiki).

For example, if we wanted to generate all the primes up to the number 30, we first create a list of numbers from 1 to 30 and follow the numbered steps:

1  2  3  4  5  6  7  8  9  10 
11 12 13 14 15 16 17 18 19 20 
21 22 23 24 25 26 27 28 29 30

(Step 1) The algorithm starts at the first number, 1, and removes it because it is not a prime number.
(Step 2) The next number is 2, which is a prime so it stays, but now all multiples of 2 are removed from the list: 4, 6, 8, 10, etc.

   2  3     5     7     9    
11    13    15    17    19    
21    23    25    27    29

(Step 3) The next number is 3, which is a prime so it stays, but now all multiples of 3 are removed from the list: 6, 9, etc.

   2  3     5     7       
11    13          17    19  
      23    25          29

(Step 4) The next number is 5, which is a prime so it stays, but now all multiples of 5 are removed from the list: 10, 15, etc.

   2  3     5     7       
11    13          17    19  
      23                29

(Step 5) All the numbers now, 7, 11, 13, etc., are all primes and there are no more multiples of numbers we can remove from the list, so we are done and the list that is left is our list of primes.

   2  3     5     7       
11    13          17    19  
      23                29
#3

okk…

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.