Eratosthenes筛法C语言实现
时间: 2024-10-04 08:01:02 浏览: 56
C语言线性筛法源代码
Eratosthenes筛法是一种古老的算法,用于找出一定范围内所有质数。在C语言中,你可以通过以下步骤来实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX 100 // 设置一个范围,例如最大查找到100内的质数
bool is_prime(int num) {
if (num <= 1)
return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0)
return false;
}
return true;
}
void sieve_of_eratosthenes() {
bool prime[MAX + 1];
memset(prime, true, sizeof(prime)); // 初始化所有数字为质数
for (int p = 2; p * p <= MAX; p++) {
// 如果p是质数,则将其倍数标记为非质数
if (prime[p]) {
for (int i = p * p; i <= MAX; i += p)
prime[i] = false;
}
}
// 输出所有的质数
for (int p = 2; p <= MAX; p++)
if (prime[p])
printf("%d ", p);
}
int main() {
sieve_of_eratosthenes();
return 0;
}
```
这个程序首先创建一个布尔数组`prime[]`,然后从2开始遍历,如果当前数是质数(即它不是2且除自身外无其他因数),就把它的倍数标记为非质数。最后,筛选出并打印出那些仍然标记为质数的数字。
阅读全文