首页筛选法求100以内素数 c语言

筛选法求100以内素数 c语言

时间: 2025-01-20 11:09:25 浏览: 74

筛选法，也叫埃拉托斯特尼筛法（Sieve of Eratosthenes），是一种古老的算法，用于查找一定范围内的所有质数。以下是使用 C 语言实现的一个简单版本，该算法逐个标记出从2到目标值（这里是100）之间的每一个合数（非质数），然后剩下的未被标记的就是素数： ```c #include <stdio.h> void sieve_of_eratosthenes(int limit) { // 初始化布尔数组表示每个数字是否是质数 int is_prime[limit + 1] = {0}; for (int i = 2; i <= limit; i++) { is_prime[i] = 1; } // 打印2作为第一个质数 printf("%d ", 2); // 对于从3开始的所有奇数，如果它们是质数，则打印并标记其后续倍数为合数 for (int i = 3; i * i <= limit; i += 2) { if (is_prime[i]) { for (int j = i * i; j <= limit; j += i * 2) { is_prime[j] = 0; } } } // 输出所有大于2的质数 for (int i = 3; i <= limit; i += 2) { if (is_prime[i]) printf("%d ", i); } } int main() { sieve_of_eratosthenes(100); return 0; } ``` 当你运行这段代码时，它会输出100以内的所有素数。

阅读全文