菜鸟建站网,财经直播网站建设,wordpress 评论数,全球最新军事动态方法一#xff1a;暴力法 思路#xff1a;从2开始#xff0c;逐个判断每个数是否为素数。素数是除了1和它自身外#xff0c;不能被其他自然数整除的数。对于每个数m#xff0c;从2到sqrt(m)遍历#xff0c;如果能被整除则不是素数。当找到n个素数时停止。 C 代码如下暴力法 思路从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 i5;i*inum;i){if(num%i0) 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;vectorbool isPrime(scope, true); // 假设一个较大的范围可根据需要调整//vectorbool 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 / l n ( n ) 1/ln(n) 1/ln(n)。 所以范围为n以内的素数个数为 n / l n ( n ) n/ln(n) n/ln(n) ,在n-无穷时成立其他情况下近似成立。 比如求第100个素数设num的范围是x则必须满足 x / l n ( x ) 100 x/ln(x)100 x/ln(x)100 解出的这个x才是我们需要的范围在这个范围内我们才能找到第100个素数。
