C语言在键盘输入一个整数n(9800&<=n<=100000),统计1至n范围内素数的个数
时间: 2023-10-08 22:07:25 浏览: 60
以下是使用C语言编写的程序,用于统计1至n范围内素数的个数:
```c
#include <stdio.h>
int isPrime(int n) {
if (n <= 1) {
return 0;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
int countPrimes(int n) {
int count = 0;
for (int i = 2; i <= n; i++) {
if (isPrime(i)) {
count++;
}
}
return count;
}
int main() {
int n;
printf("请输入一个整数n(9800<=n<=100000): ");
scanf("%d", &n);
int count = countPrimes(n);
printf("1至%d范围内素数的个数是: %d\n", n, count);
return 0;
}
```
程序中,我们定义了两个函数,`isPrime`函数用于判断一个数是否是素数,`countPrimes`函数用于统计1至n范围内素数的个数。
在`isPrime`函数中,我们首先判断如果n小于等于1,则直接返回0,因为1不是素数。然后我们从2开始循环到sqrt(n)(sqrt表示开平方),如果n可以整除i,则n不是素数,返回0,否则n是素数,返回1。
在`countPrimes`函数中,我们从2开始循环到n,对于每个数i,如果它是素数,则计数器加1。
在主函数中,我们首先从用户输入中获取n的值,然后调用`countPrimes`函数统计1至n范围内素数的个数,并打印输出结果。
注意:由于题目要求输入的n的范围比较大,我们需要保证程序的时间复杂度较小,这里我们使用了“埃氏筛法”的时间复杂度较优的算法。如果您想了解更多有关“埃氏筛法”的内容,请自行搜索相关资料。