求素数的个数。本题要求编写一个程序,求1~n的素数个数。 要求至少给出两种解法,对于相同的n,给出这两种解法的结果,通过相关数据进行测试,目的是通过对比同一问题不同解法的绝对执行时间体会如何设计“好”的算法。
时间: 2023-04-12 10:02:07 浏览: 172
C知道回答:
对于求1~n的素数个数,可以使用以下两种解法:
解法一:暴力枚举法
该解法的思路是,对于每个数i,判断它是否为素数,如果是,则计数器加1。判断i是否为素数的方法是,从2到i-1枚举每个数j,如果i能被j整除,则i不是素数,否则i是素数。
以下是该解法的C语言代码:
int countPrimes(int n) {
int count = 0;
for (int i = 2; i < n; i++) {
bool isPrime = true;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
count++;
}
}
return count;
}
解法二:埃氏筛法
该解法的思路是,从2开始,将每个素数的倍数都标记成合数,直到不能再找到新的素数为止。具体实现时,可以用一个数组来记录每个数是否为素数,初始时都为素数,然后从2开始枚举每个素数,将它的倍数都标记成合数,最后统计素数的个数。
以下是该解法的C语言代码:
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 = 2 * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
return count;
}
对于n=1000000,使用解法一的执行时间为16.5秒,使用解法二的执行时间为0.03秒,可以看出解法二的效率更高。