shivambhatele Posted July 14 Share Posted July 14 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

sama Posted July 14 Share Posted July 14 (edited) 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 by sama Link to comment

atom0s Posted July 14 Share Posted July 14 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 1 Link to comment

## Recommended Posts

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