Jump to content

Sieve of Eratosthenes in C++


shivambhatele

Recommended Posts

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 << " ";
}

 

Link to comment

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 by sama
Link to comment

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

  • Like 1
Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...