eratosthenes筛法求素数c语言代码
时间: 2024-05-07 13:23:11 浏览: 9
下面是使用 Eratosthenes 筛法求素数的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int main()
{
int n;
printf("请输入要求素数的范围 n:\n");
scanf("%d", &n);
bool *is_prime = (bool*)malloc(sizeof(bool) * (n + 1)); // 动态分配布尔型数组
for (int i = 2; i <= n; i++) {
is_prime[i] = true; // 先默认都是素数
}
for (int i = 2; i * i <= n; i++) { // 只需要枚举到 sqrt(n)
if (is_prime[i]) { // 如果 i 是素数
for (int j = i * i; j <= n; j += i) { // 将 i 的倍数标记为合数
is_prime[j] = false;
}
}
}
printf("2~%d 范围内的素数有:\n", n);
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
printf("%d ", i);
}
}
printf("\n");
free(is_prime); // 释放动态分配的内存
return 0;
}
```
该程序的思路就是,先将所有数都标记为素数,然后从 2 开始枚举,如果当前数为素数,则将它的倍数标记为合数。最后输出所有未被标记为合数的数,即为素数。