首页c语言筛选法求素数

c语言筛选法求素数

时间: 2025-04-27 07:24:00 浏览: 36

### C语言实现筛选法求素数为了利用埃拉托斯特尼筛法在C语言中找出一定范围内的所有素数，可以通过如下方式构建程序： ```c #include <stdio.h> int main() { int i, j; const int MAX = 400000; // 设定最大值 int num[MAX + 1]; // 创建一个足够大的数组来保存状态 // 初始化数组中的所有元素为0，表示尚未标记 for (i = 2; i <= MAX; ++i) { num[i] = 0; } // 开始应用埃拉托斯特尼筛法 for (i = 2; i * i <= MAX; ++i) { if (!num[i]) { // 当前索引未被标记，则认为是素数 for (j = i * i; j <= MAX; j += i) { num[j] = 1; // 将此素数的所有倍数标记为非素数 } } } // 输出所有的素数 printf("Prime numbers between 2 and %d are:\n", MAX); for (i = 2; i <= MAX; ++i) { if (!num[i]) { printf("%d ", i); // 只打印那些仍然保持初始值（即素数） } } return 0; } ``` 上述代码展示了如何通过埃拉托斯特尼筛法高效地找到并打印给定范围内所有素数[^1]。 #### 关键点解释 - **初始化阶段**：创建了一个大小为`MAX+1`的数组用于记录各个数值的状态。默认情况下，除了0和1以外的位置都被设为可能的素数。 - **核心逻辑**：遍历从2到√N之间每一个未曾被处理过的数字作为起点，将其平方及其后的所有倍数都标记成合数；因为更小的乘积已经在之前的轮次中标记过了。 - **输出结果**：最后再次扫描整个列表，仅保留那些从未被修改过位置上的原始编号，这些就是最终确认下来的全部素数。这种方法相比暴力枚举具有更高的效率，在实际编程竞赛或者大规模数据处理场景下非常有用。

阅读全文