用c语言计算出1-100内素数(素数,又称质数,即整数在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数)的总数
时间: 2024-10-10 22:16:51 浏览: 87
输入整数n,输出1~n的素数
在C语言中计算1到100之间素数的数量,我们可以使用一个经典的算法,称为“埃拉托斯特尼筛法”(Sieve of Eratosthenes)。这个算法通过标记每个合数(非素数)的倍数,然后遍历列表,找出未被标记的所有数字,它们就是素数。
以下是简单的C语言代码实现:
```c
#include <stdio.h>
int is_prime(int num) {
if (num <= 1)
return 0;
for (int i = 2; i * i <= num; i++) { // 只需检查到sqrt(num),因为大于该值的因子一定会有一个小于等于sqrt(num)
if (num % i == 0)
return 0;
}
return 1;
}
int count_primes(int n) {
int count = 0;
int limit = sqrt(n); // 筛选出1到limit内的数
for (int i = 2; i <= limit; i++) {
if (is_prime(i)) {
count++; // 如果i是素数,计数加1
for (int j = i * i; j <= limit; j += i) { // 将i的倍数标记为合数
if (j > n) break;
if (is_prime(j))
count--; // 因为j不是素数,所以已计数的素数需要减去
}
}
}
return count + is_prime(n); // 最后别忘了n可能是素数
}
int main() {
int primes_in_1_to_100 = count_primes(100);
printf("1到100内素数的总数为:%d\n", primes_in_1_to_100);
return 0;
}
```
在这个程序中,`is_prime`函数用于判断是否为素数,`count_primes`函数则通过埃拉托斯特尼筛法计算1到指定范围内的素数数量。运行这段代码,将得到1到100内素数的总数。
阅读全文