求从2开始的第n个素数

方法一：暴力法

• 思路：从2开始，逐个判断每个数是否为素数。素数是除了1和它自身外，不能被其他自然数整除的数。对于每个数m，从2到sqrt(m)遍历，如果能被整除则不是素数。当找到n个素数时停止。

• C++ 代码如下：

#include <iostream>
#include <cmath>
using namespace std;bool isPrime(int num) {if (num <= 1) return false;if (num <= 3) return true;if (num % 2 == 0 || num % 3 == 0) return false;/*for (int i = 5; i * i <= num; i = i + 6) {if (num % i == 0 || num % (i + 2) == 0) return false;}*/for(int i=5;i*i<=num;i++){if(num%i==0) return false;}return true;
}int nthPrime(int n) {int count = 0;int num = 2;while (true) {if (isPrime(num)) {count++;if (count == n) return num;}num++;}return -1;
}int main() {int n;cout << "Enter the value of n: ";cin >> n;cout << "The " << n << "th prime number is: " << nthPrime(n) << endl;return 0;
}

方法二：埃氏筛法（Sieve of Eratosthenes）改进

• 思路：先创建一个足够大的布尔数组来标记数是否为素数。从2开始，将2的倍数标记为非素数，然后找到下一个未标记的数（即素数），重复这个过程。当找到n个素数时，可以得到第n个素数的值。

• C++ 代码如下：

#include <iostream>
#include <vector>
using namespace std;int nthPrime(int n) {if (n == 1) return 2;int scope = 100;int x = (int)(scope / log(scope));while (x < n) {scope++;x = (int)(scope / log(scope));}cout<< "scope: " << scope << endl;vector<bool> isPrime(scope, true);  // 假设一个较大的范围，可根据需要调整//vector<bool> isPrime(1000000, true);  // 假设一个较大的范围，可根据需要调整isPrime[0] = isPrime[1] = false;int count = 0;for (int i = 2; i < isPrime.size(); i++) {if (isPrime[i]) {count++;if (count == n) return i;for (int j = i * i; j < isPrime.size(); j += i) {isPrime[j] = false;}}}return -1;
}int main() {int n;cout << "Enter the value of n: ";cin >> n;cout << "The " << n << "th prime number is: " << nthPrime(n) << endl;return 0;
}

这两种方法中，埃拉托斯特尼筛法在处理较大的n值时效率更高，因为它避免了对许多数的重复判断。但需要注意内存使用情况，如果n非常大，可能需要更复杂的数据结构或算法优化。

拓展与总结：

• 从不大于 n 的自然数随机选一个，它是素数的概率大约是 $1/ln(n)$。
  所以范围为n以内的素数个数为$n/ln(n)$ ,在n->无穷时成立，其他情况下近似成立。

• 比如求第100个素数，设num的范围是x，则必须满足$x/ln(x)>=100$ ，解出的这个x才是我们需要的范围，在这个范围内我们才能找到第100个素数。