用C语言求某个区间内素数的个数
时间: 2023-09-14 07:09:16 浏览: 184
可以使用筛法求解某个区间内的素数个数。具体步骤如下:
1. 定义一个 bool 类型的数组 isPrime,用于标记某个数是否为素数,初始值全部设为 true;
2. 从 2 开始,遍历到区间右端点 right,对每个数进行以下操作:
1. 如果该数是素数,将其所有的倍数(除了本身)都标记为非素数;
2. 如果该数不是素数,则直接跳过;
3. 遍历完区间后,统计 isPrime 数组中 true 的个数,即为该区间内的素数个数。
以下是 C 语言代码实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_N 1000000
bool isPrime[MAX_N + 1];
int countPrimes(int left, int right) {
int cnt = 0;
// 初始化
for (int i = 2; i <= right; i++) {
isPrime[i] = true;
}
// 筛法求素数
for (int i = 2; i <= right; i++) {
if (isPrime[i]) {
if (i >= left && i <= right) {
cnt++;
}
for (int j = i * 2; j <= right; j += i) {
isPrime[j] = false;
}
}
}
return cnt;
}
int main() {
int left = 1, right = 100;
int cnt = countPrimes(left, right);
printf("There are %d primes in [%d, %d].\n", cnt, left, right);
return 0;
}
```
注意,该算法的时间复杂度为 O(n log log n),其中 n 表示区间长度。对于较大的区间,可能需要较长的时间才能计算出结果。