Find the nth prime number 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 &lt;map&gt;

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&lt;unsigned long, unsigned long&gt;();
    // The overflow tests below are valid only for unsigned types.
    for (auto i = 3ul;  true;  i += 2) {
        if (i &lt; 3ul)            // overflow test
            throw std::overflow_error("prime too large");

        const auto it = m.cbegin();
        if (it == m.end() || it-&gt;first != i) {
            // it's a prime
            if (!--n)
                return i;
            if (i*i &gt; i)        // overflow test
                m.insert({i*i, 2*i});
        } else {
            // it's composite - advance the factor
            auto next = it-&gt;first;
            do {
                next += it-&gt;second;
            } while (next &gt; i &amp;&amp; !m.emplace(next, it-&gt;second).second);
            m.erase(it);
        }
    }
}


And the test program (not really part of the review):

#include &lt;iostream&gt;
#include &lt;string&gt;

int main(int, char **argv)
{
    std::cout.imbue(std::locale(""));
    while (*++argv) {
        try {
            std::cout &lt;&lt; find_nth_prime(std::stoul(*argv)) &lt;&lt; std::endl;
        } catch (std::exception&amp;) {
            std::cerr &lt;&lt; "Invalid argument: " &lt;&lt; *argv &lt;&lt; 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.
Bug: Only works if longs are 64-bit

I ran your program on my 32-bit machine and got the wrong answer for the 1 millionth prime: 15498907 instead of 15485863.  The problem is here:


        if (i*i &gt; i)        // overflow test



If longs are 32 bits, then a number such as 0x10001 will pass this overflow test (because 0x10001 * 0x10001 = 0x20001 after overflowing).  This eventually causes problems because overflowed values are inserted into the map.  Actually, even if longs are 64-bit, you will still have a problem, but it will only happen after i reaches 0x100000001.

I fixed the problem by doing this:

    unsigned long max_i = std::sqrt(~0UL);
    // ...
        if (i &lt;= max_i)      // overflow test


Slow compared to vector based solution

I found your program to be a lot slower than a traditional vector based sieve.  Here are timings for your program vs a traditional sieve that I wrote which used a vector&lt;bool&gt;:

Map    based,  1 millionth prime:  3.77 seconds
Map    based, 10 millionth prime: 47.91 seconds
Vector based,  1 millionth prime:  0.04 seconds
Vector based, 10 millionth prime:  0.93 seconds


Sample vector based code

Since there was a comment asking about how the vector based code would work, here is the full program I used:

#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;cstdlib&gt;
#include &lt;cmath&gt;
#include &lt;cstdio&gt;
#include &lt;vector&gt;

// This function uses the prime counting function approximation:
//
// n = x / ln(x)
//
// Where n is the number of primes below the number x.  Since we are trying
// to find the nth prime, we should solve for x here to determine an
// approximate value for the nth prime.  It turns out that for n &gt;= 6, the
// value we solve for x will always be larger than the nth prime value.
//
// If the sieve size doesn't fit in an unsigned long, this function returns 0.
unsigned long findSieveSize(unsigned long n)
{
    // For small n, the formula returns a value too low, so we can just
    // hardcode the sieve size to 5 (5th prime is 11).
    if (n &lt; 6)
        return 13;

    // We can't find a prime that will exceed ~0UL.
    if (n &gt;= (~0UL / std::log(~0UL)))
        return 0;

    // Binary search for the right value.
    unsigned long low  = n;
    unsigned long high = ~0UL - 1;
    do {
        unsigned long mid   = low + (high - low) / 2;
        double        guess = mid / std::log(mid);

        if (guess &gt; n)
            high = (unsigned long) mid - 1;
        else
            low = (unsigned long) mid + 1;
    } while (low &lt; high);
    return high + 1;
}

unsigned long find_nth_prime(unsigned long n)
{
    if (!n) return 1;           // "0th prime"
    if (!--n) return 2;         // first prime

    unsigned long sieveSize = findSieveSize(n);
    unsigned long count     = 0;
    unsigned long max_i     = std::sqrt(sieveSize-1)+1;

    if (sieveSize == 0)
        return 0;

    std::vector&lt;bool&gt; sieve(sieveSize);
    for (unsigned long i = 3;  true;  i += 2) {
        if (!sieve[i]) {
            if (++count == n)
                return i;
            if (i &gt;= max_i)
                continue;
            unsigned long j    = i*i;
            unsigned long inc  = i+i;
            unsigned long maxj = sieveSize - inc;
            // This loop checks j before adding inc so that we can stop
            // before j overflows.
            do {
                sieve[j] = true;
                if (j &gt;= maxj)
                    break;
                j += inc;
            } while (1);
        }
    }
    return 0;
}

int main(int, char **argv)
{
    std::cout.imbue(std::locale(""));
    while (*++argv) {
        try {
            std::cout &lt;&lt; find_nth_prime(atoi(*argv)) &lt;&lt; std::endl;
        } catch (std::exception&amp;) {
            std::cerr &lt;&lt; "Invalid argument: " &lt;&lt; *argv &lt;&lt; std::endl;
        }
    }
}