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 -WpedanticWhilst 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.
Find the nth prime number
c++;primes;sieve of eratosthenes
Bug: Only works if longs are 64-bitI 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 > i)        // overflow testIf 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 = sqrt(~0UL);    // ...        if (i <= max_i)      // overflow testSlow compared to vector based solutionI 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<bool>:Map    based,  1 millionth prime:  3.77 secondsMap    based, 10 millionth prime: 47.91 secondsVector based,  1 millionth prime:  0.04 secondsVector based, 10 millionth prime:  0.93 secondsSample vector based codeSince there was a comment asking about how the vector based code would work, here is the full program I used:#include <iostream>#include <string>#include <cstdlib>#include <cmath>#include <cstdio>#include <vector>// 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 >= 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 < 6)        return 13;    // We can't find a prime that will exceed ~0UL.    if (n >= (~0UL / 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 / log(mid);        if (guess > n)            high = (unsigned long) mid - 1;        else            low = (unsigned long) mid + 1;    } while (low < 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     = sqrt(sieveSize-1)+1;    if (sieveSize == 0)        return 0;    std::vector<bool> sieve(sieveSize);    for (unsigned long i = 3;  true;  i += 2) {        if (!sieve[i]) {            if (++count == n)                return i;            if (i >= 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 >= maxj)                    break;                j += inc;            } while (1);        }    }    return 0;}int main(int, char **argv){    std::cout.imbue(std::locale());    while (*++argv) {        try {            std::cout << find_nth_prime(atoi(*argv)) << std::endl;        } catch (std::exception&) {            std::cerr << Invalid argument:  << *argv << std::endl;        }    }}