找第n小质数 c++

在C++中，找到第n个最小的质数可以使用多种算法，一种常见的方法是结合Sieve of Eratosthenes筛法和动态查找。以下是简单的步骤：

1. **Sieve of Eratosthenes**:
- 初始化一个布尔数组，大小为你要找的质数范围，初始值全部设为true，表示所有数字都是潜在的质数。
- 遍历数组，从第一个未标记的数（即2开始），将它的倍数都标记为非质数，直到sqrt(n)。
- 这样剩下的未被标记的数就是质数。

2. **寻找第n个质数**:
- 使用一个计数器`count`初始化为0，遍历筛法后的数组。
- 当发现一个新的质数时，增加`count`，如果`count`达到n，则找到了第n个质数，并返回它。

下面是伪代码和简单示例：

#include <vector>
using namespace std;

int nthPrime(int n) {
    if (n <= 0) return 0; // 第0个质数不存在

    int limit = sqrt(n); // 筛法范围上限
    vector<bool> isPrime(limit + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= limit; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i)
                isPrime[j] = false;
        }
    }

    int count = 0;
    for (int i = 2; i <= limit; ++i) {
        if (isPrime[i])
            count++;
        if (count == n)
            return i;
    }

    // 如果n大于实际的质数数量，返回最大质数
    return count > n ? limit : nthPrime(n); // 如果没有找到第n个质数，递归查询
}