Sieve of Eratosthenes

[CoderGirlV]

Can someone explain the "Sieve of Eratosthenes" to me. I'm a bit confused on what I am suppose to do. Is it just printing out 1 to max using for loops?

Create a program to find all the prime numbers between 1 and max . This time, use a classic method called the ”Sieve of Eratosthenes.”


Thank you in advance!

[tallyman]

The wikipedia page has a good description https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

Essentially, you create a list of numbers, 2 to max.
Then, you iterate over the numbers.
If the number is in the list, check all the multiples of the number.
If any there are any multiples of the number in the list, remove them.
If you removed any multiples, you move onto the next number in the list that hasn't been removed.
If you didn't remove any multiples, then all numbers that have not been removed from the list are prime.

[CoderGirlV]

So to make sure that I am understanding Sieve of Eratosthenes correctly, is this code correct?

#include "std_lib_facilities.h"
int main()
{
    bool A[100];
    int n;
    cout << "Enter a number: " << endl;
    cin >> n;

    for(int i = 1; i < n; i++)
        A[i] = true;

    for(int i = 2; i < sqrt(n); i++)
    {
        if (A[i] == true)
        {
            for (int j = i * i; j < n; j+= i)
            {
                A[j] = false;
            }
        }
    }

    cout << "The prime numbers below " << n << " are: " << endl;
    
    for(int i = 1; i <n; i++)
    {
        if (A[i] == true)
        {
            cout << i << " ";
        }
    }

    cout << endl;
    
    return 0;
    
}

Since question asked for 1 - max to print. Is there a way to do this without using an array?

[mbozzi]

Is this code correct?

Yes, the algorithm is basically correct, as long as the user enters a small number (n <= 100).
The only flaw is that 1 is not prime.

Is there a way to do this without using an array?

No. Well, it doesn't necessarily have to be an array -- some other structures could work (although many would perform worse), but all prime sieves start with a large collection of possibilities and "filter-out" candidates that are eliminated.

In general, there is no easily-computable implicit or explicit formula for prime numbers that we know of.