写一段C++埃氏筛法
时间: 2023-11-14 22:06:08 浏览: 43
以下是使用C语言实现的埃氏筛法:
```c
#include <stdio.h>
void sieveOfEratosthenes(int n) {
// 创建一个标志数组,用于标记是否为质数
int prime[n+1];
for (int i = 0; i <= n; i++) {
prime[i] = 1; // 初始化所有数字都假设为质数
}
// 将标志数组中的合数索引置为0
for (int p = 2; p * p <= n; p++) {
if (prime[p] == 1) {
// 将p的倍数标记为合数
for (int i = p * p; i <= n; i += p) {
prime[i] = 0;
}
}
}
// 输出所有的质数
printf("2 "); // 2是唯一的偶数质数,直接输出
for (int p = 3; p <= n; p += 2) {
if (prime[p] == 1) {
printf("%d ", p);
}
}
}
int main() {
int n;
printf("请输入一个正整数n:");
scanf("%d", &n);
printf("小于等于%d的所有质数为:\n", n);
sieveOfEratosthenes(n);
return 0;
}
```