Vector of bools

sieve.h

#if !defined(SIEVE_H)
#define SIEVE_H
#include <vector>
namespace sieve {
    std::vector<int> primes(int);
}  // namespace sieve
#endif // SIEVE_H

sieve.cpp

#include "sieve.h"

namespace sieve {

	std::vector<int> primes(int limit) {
		std::vector<bool> composite(limit + 1, false);
		std::vector<int> primes;
		primes.reserve(limit / 2);
    
		for (int number = 2; number <= limit; number++) {
			if (!composite[number]) {
				primes.emplace_back(number);
				for(int idx = number * number; idx <= limit; idx +=number)
					composite[idx] = true;
			}
		}
		return primes;
	}
}  // namespace sieve

This approach starts by defining a vector to keep track of the composite numbers, with the elements initialized to false. The output vector is also defined, and then the reserve method is used to set its capacity to half of the limit, since at least half of the numbers will be even and so not prime.

Since values less than 2 are not prime, the iteration of the outer for loop begins at 2. If the number being iterated is not a composite number, then the emplace_back method is used to append the number being iterated to the output vector.

Since any number evenly divisible by that prime is not prime, the inner for loop iterates from the prime times itself, setting each of the elements at that index to true for being a composite number.

After the outer loop is done, the vector of primes is returned.