Sieve of Eratosthenes in C++

[shivambhatele]

Hello All, I am new in this community and I working on a freelance C++ project and I am confused sieve of eratosthenes coding problem. The problem statement is Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number. I am trying to solve this problem by Efficient Approach

A prime number is a number that is divisible by only two numbers – themselves and 1
Example:
Input: n =10
Output: 2 3 5 7

I have checked sieve of eratosthenes coding problem on google and I have found this problem post. I am sharing one code example. Can anyone explain me, how sieve of eratosthenes program works? or explain with another example?

void SieveOfEratosthenes(int n)
{
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p <= n; p++)
        if (prime[p])
            cout << p << " ";
}

 

[sama]

knowing that #2 is the only even number, then you can focus on odd numbers.

For checking odds test bit 0, if set then is odd, if that the case save that number and remove all multiples of it.

How long should that be done? >>> max till isqrt of n !

 

 

 

 

Edited July 16, 2022 by sama

[atom0s]

Wikipedia has a page covering how the sieve works here: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Along with all the references linked on the bottom of that page which further detail and explain it in various degrees. 

Other sites with code examples and other explainations:

https://www.geeksforgeeks.org/sieve-of-eratosthenes/
https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html
https://www.delftstack.com/howto/cpp/sieve-of-eratosthenes-in-cpp/
https://www.journaldev.com/61127/sieve-of-eratosthenes-cpp

You'll notice in a lot of the examples you can find online that the implementations for C++ will use std::vector<bool> as the container. This is done because C++ has a specialization where if a vector is being used with a bool type, then it will be automatically treated as a bitset and reduce the storage space even further. You can read more about that here:

https://en.cppreference.com/w/cpp/container/vector_bool