Sieve of Eratosthenes for primes up to 100

Question

#include <iostream>
#include <vector>

int main()
{
    vector<int> primes;

    int n = 100;     // amount of numbers - 1
    vector<bool> sieve;
    for (int i = 0; i <= n; i++) {   // creating vector with all true values
        sieve.push_back(true);
    }

    // let's set 0 and 1 to false because well we know they're not prime already.
    sieve[0] = false;
    sieve[1] = false;

    // we'll make it so all elements that are set to true are prime numbers.
    int p = 2;     // setting p to first prime number.

    while (p != 11) {
        int i = 2 * p;
        for (int j = 1; j <= (n / p) - 1; j++) { // sets all p's multiples to false.
            sieve[i] = false;
            i = i + p;
        }
        for (int i = 2; i <= 100; i++) { // checking for first number greater than p
            // that is prime and setting p equal to it
            if (sieve[i] == true && i > p) {
                p = i;
                break;
            }
        }
    }

    for (int i = 0; i < sieve.size(); i++) {
        if (sieve[i] == true) { // if the number is prime:
            primes.push_back(i); // put it into the primes vector.
        }
    }

    for (int x: primes) {
        cout << x << endl;
    }
    cin >> n;
}

First question: Is this like a terrible way to implement the algorithm? I had trouble doing this and finally came up with this solution but I don't know if it's terrible and a very bad way.

Second question: do you know how I can possibly change the while condition to make it more flexible? In my case I made it p!=11 because in the range 1-100 there's no point in checking for primes after 7; the program will find the next prime after 7 to be 11 but I'll stop it from continuing. If I want to make it keep going I'll have to change the while loop condition or find some solution to make it stop running after it's found all primes in the range; how can I do this?

Answer 1

std::vector<bool> isn't a great idea. It doesn't work like a standard container (despite the very similar name). std::vector<char> will be faster, and we can almost certainly afford the space when n is 100. Alternatively, change to constexpr n, and we can use a fixed-size container such as std::array<bool,n> (which is a standard container) or std::bitset<n>.

If we're using std::vector, we should avoid it reallocating. We could do this with a sieve.reserve() before the push_back() loop, or we could populate the sieve like this:

vector<bool> sieve(n, true);

// 0 and 1 non-prime
sieve[0] = false;
sieve[1] = false;

Inverting the sense (so true in the sieve means "composite" rather than "prime") simplifies the initialization, because default-initialisation is to false.

The test while (p != 11) is tightly tied to the size of the sieve. A better test would be while (p <= sieve.size() / p) - though we'll want an unsigned type for p to avoid problems with mixed-signedness arithmetic (std::size_t is an unsigned type).

The "marking" phase can be simplified:

    int i = 2 * p;
    for (int j = 1;  j <= (n / p) - 1;  j++) { // sets all p's multiples to false.
        sieve[i] = false;
        i = i + p;
    }

Instead of introducing the new variable j, why not use i as the control? Like this:

    for (unsigned int i = 2 * p;  i < n;  i += p) {
        sieve[i] = false;
    }

And we don't need to start at 2 * p because we know that every multiple less than p² has already been crossed off - so replace that with p * p.

The following loop doesn't need to start at the beginning every time:

    for (int i = 2; i <= 100; i++) { // checking for first number greater than p
        // that is prime and setting p equal to it
        if (sieve[i] == true && i > p) {
            p = i;
            break;
        }
    }

We can replace with for (i = p + 1; i < n; ++i) to search beginning just after p. Or since we're using this to find the next p, just

    // increase p to next prime
    while (!sieve[++p])
        ;

We could even just put that test at the start of the main loop:

while (p <= sieve.size() / p) {
    if (!sieve[p]) {
        continue;
    }
    for (unsigned int i = p * p;  i < n;  i += p) {
        sieve[i] = false;
    }
}

There seems no need for the primes variable. All we do is push the primes into it, then read them back to print them. We could just print as we go:

for (unsigned i = 0;  i < sieve.size();  ++i) {
    if (sieve[i]) {
        std::cout << i << '\n';
    }
}

Or even just within the main p loop - though we'll need to make that continue up to the end rather than stopping at √n. (That's not such a big overhead once we've changed the striking off to begin at p², of course).

Note there's no need to flush every line with std::endl - plain newline is less wasteful.

Why do we attempt to read a value into n? That is utterly pointless, as it's never used.

We can halve the number of loops executed by first marking all even numbers (apart from 2), and then incrementing by twice what we were.

---

Modified code

Simpler and more efficient:

#include <array>
#include <iostream>

int main()
{
    constexpr std::size_t n = 100;
    std::array<bool,n> sieve{};   // true means composite

    // mark all even numbers
    for (std::size_t i = 4;  i < n;  i += 2) {
        sieve[i] = true;
    }
    std::cout << "2\n";

    for (std::size_t p = 3;  p < n;  p += 2) {
        if (sieve[p]) {
            // composite
            continue;
        }
        // it's prime!
        std::cout << p << '\n';
        // remove its multiples
        for (std::size_t i = p * p;  i < n;  i += p * 2) {
            sieve[i] = true;
        }
    }
}

Answer 2

1. You are missing std:: on some of the elements; it should be:

   std::vector<int> primes;
   

2. Instead of using a for loop to push the values into the vector one at a time, you can use the 'fill' constructor:

   std::vector<bool> sieve(n + 1, true);
   

3. Create a function that is reusable:

   std::vector<int> calcPrimes(int n) {
       std::vector<int> primes;
       ...
       return primes;
   }
   
   int main()
   {
       std::vector<int> primes = calcPrimes(100);
       for (int x : primes) 
           std::cout << x << "\n";
   }
   

4. Magic Numbers - what is the significance of 11 here? If n was less than 11, this would have resulted in an endless loop.

    while (p != 11) {
   

   Consider replacing it with:

        int minRoot = std::sqrt(n);
        while (p <= minRoot) {
            ...
   

5. I'm assuming that the following line:

        for (int i = 2; i <= 100; i++) {
   

   should have been:

        for (int i = 2; i <= n; i++) {
   

   You may also consider using std::find() instead of this loop.