It's a long time since I've written a Sieve of Eratosthenes (about 3 decades, I think, in ZX Basic). So I decided to revisit in the light of experience.
Rather than allocating a vector of unknown size to sieve values, I keep an ordered set of upcoming composite values which are updated as they are reached.
#include <map>
unsigned long find_nth_prime(unsigned long n)
{
if (!n) return 1; // "0th prime"
if (!--n) return 2; // first prime
// The map m contains one entry for each prime. The key is the
// next time to update it, and the value is the amount to increment
// by each time it is reached.
auto m = std::map<unsigned long, unsigned long>();
// The overflow tests below are valid only for unsigned types.
for (auto i = 3ul; true; i += 2) {
if (i < 3ul) // overflow test
throw std::overflow_error("prime too large");
const auto it = m.cbegin();
if (it == m.end() || it->first != i) {
// it's a prime
if (!--n)
return i;
if (i*i > i) // overflow test
m.insert({i*i, 2*i});
} else {
// it's composite - advance the factor
auto next = it->first;
do {
next += it->second;
} while (next > i && !m.emplace(next, it->second).second);
m.erase(it);
}
}
}
And the test program (not really part of the review):
#include <iostream>
#include <string>
int main(int, char **argv)
{
std::cout.imbue(std::locale(""));
while (*++argv) {
try {
std::cout << find_nth_prime(std::stoul(*argv)) << std::endl;
} catch (std::exception&) {
std::cerr << "Invalid argument: " << *argv << std::endl;
}
}
}
Compiled with GCC:
g++ -std=c++17 -O3 -Wall -Wextra -Wpedantic
Whilst the performance is acceptable (about 1.6 seconds on my hardware to find the one-millionth prime - 15,485,863), I'm unsure whether a std::map
is really the best structure for keeping track. As usual, any other critique of the code is welcome.
invalid_argument
there, I think. \$\endgroup\$ – Toby Speight Feb 2 '17 at 17:22