C语言实现高效素数筛选与输出56

素数，又称质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。素数的分布是数论中的一个核心问题，也是计算机科学中许多算法的基础。本文将深入探讨如何在C语言中高效地筛选并输出素数，并分析不同算法的优缺点。

最简单的素数判断方法是试除法，即依次检查从2到n-1的每个数是否能整除n。如果都不能整除，则n是素数。这种方法虽然简单易懂，但效率低下，尤其对于大的n值，时间复杂度高达O(n)。因此，对于需要筛选大量素数的情况，试除法并不适用。

为了提高效率，我们可以采用更高级的算法，例如埃拉托斯特尼筛法（Sieve of Eratosthenes）。该算法的核心思想是：首先创建一个从2到n的布尔数组，初始时所有元素都标记为true。然后，从2开始，依次遍历每个数：如果一个数是素数（其对应的布尔值为true），则将其所有倍数都标记为false。遍历完成后，所有标记为true的数就是素数。

以下是使用埃拉托斯特尼筛法在C语言中筛选素数的代码：```c
#include
#include
#define MAXN 10000 // 可以根据需要调整上限
int main() {
bool is_prime[MAXN + 1];
for (int i = 2; i

2025-03-28

上一篇：C语言中空格的输出与处理详解

下一篇：C语言绘制各种图形矩形：从基础到进阶