Jump to content
View in the app

A better way to browse. Learn more.

Tuts 4 You

A full-screen app on your home screen with push notifications, badges and more.

To install this app on iOS and iPadOS
  1. Tap the Share icon in Safari
  2. Scroll the menu and tap Add to Home Screen.
  3. Tap Add in the top-right corner.
To install this app on Android
  1. Tap the 3-dot menu (⋮) in the top-right corner of the browser.
  2. Tap Add to Home screen or Install app.
  3. Confirm by tapping Install.

Sieve of Eratosthenes in C++

Featured Replies

Posted

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

 

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

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

Create an account or sign in to comment

Configure browser push notifications

Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.