本文将详细阐述两种求素数的个数的解法，分别是暴力枚举法和埃氏筛法，并对它们的时间复杂度和应用场景进行分析。
一、暴力枚举法
暴力枚举法是最朴素的解法，从2开始，依次枚举2~n中的每一个数，判断它是否为素数，如果是，素数个数+1。判断某个数是否为素数，可以用它是否能被2~根号n之间的任意一个整数整除来判断。
int countPrimes(int n) {
int count = 0;
for(int i = 2; i < n; i++) {
bool isPrime = true;
for(int j = 2; j <= sqrt(i); j++) {
if(i % j == 0) {
isPrime = false;
break;
}
}
if(isPrime)
count++;
}
return count;
}
时间复杂度为O(n*sqrt(n))，空间复杂度为O(1)。显然，暴力枚举法并不适用于大规模的数据。
二、埃氏筛法
埃氏筛法是一种简单而高效的筛法，它通过一个布尔数组来记录每个数字是否为素数，初始时将所有元素设为true，从2开始，依次枚举2~n中的每个数，如果该数为素数，则将它的倍数都标记为非素数。最后，统计布尔数组中true的个数即可。
int countPrimes(int n) {
bool isPrime[n];
memset(isPrime, true, sizeof(isPrime));
int count = 0;
for(int i = 2; i < n; i++) {
if(isPrime[i]) {
count++;
for(int j = i*i; j < n; j += i)
isPrime[j] = false;
}
}
return count;
}
时间复杂度为O(n*log(log(n)))，空间复杂度为O(n)。相比于暴力枚举法，埃氏筛法在处理大规模数据时表现更优秀。
三、总结
以上是两种求素数的个数的解法，暴力枚举法适用于小规模数据，时间复杂度较高，在处理大规模数据时会出现超时等问题；而埃氏筛法是一种高效的筛法，其时间复杂度较低，处理大规模数据时表现更加卓越。
原创文章，作者：UGUDM，如若转载，请注明出处：https://www.506064.com/n/373077.html
微信扫一扫 
支付宝扫一扫 