Visit the sieve exercise on Exercism to read the full instructions and download the exercise files.
Dig Deeper
Vector of bools
vector of bools
sieve.h
#pragma once
#include <vector>
namespace sieve {
std::vector<int> primes(int);
} // namespace sieve
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.
Source: Exercism cpp/sieve