引言
素数，也被称为质数，是指只能被1和它本身整除的大于1的自然数。在计算机科学和数学中，求素数是一个经典问题，它不仅考验算法的效率，也体现了编程技巧。本文将深入探讨在C语言中如何高效地求出999以内的所有素数，并揭秘其中的算法奥秘。
算法概述
求素数有多种算法，其中最简单的是试除法。然而，试除法的时间复杂度较高，不适合大范围求解。为了提高效率，我们可以采用以下几种算法：
埃拉托斯特尼筛法（Sieve of Eratosthenes）
暴力枚举法
概率性算法（如Miller-Rabin素性测试）
本文将重点介绍埃拉托斯特尼筛法，因为它在求小范围内素数时非常高效。
埃拉托斯特尼筛法
埃拉托斯特尼筛法是一种古老但高效的算法，用于找出小于或等于给定数的所有素数。以下是该算法的步骤：
创建一个布尔数组，标记从2到n的所有数。
从2开始，将所有2的倍数（除了2本身）标记为非素数。
寻找下一个未被标记的数，然后将其所有倍数标记为非素数。
重复步骤3，直到遍历所有数。
未被标记的数即为素数。
C语言实现
下面是使用埃拉托斯特尼筛法在C语言中求999以内所有素数的示例代码：
#include
#include
#include
#define MAX_NUM 999
int main() {
bool is_prime[MAX_NUM + 1];
memset(is_prime, true, sizeof(is_prime));
for (int i = 2; i * i <= MAX_NUM; i++) { if (is_prime[i]) { for (int j = i * i; j <= MAX_NUM; j += i) { is_prime[j] = false; } } } for (int i = 2; i <= MAX_NUM; i++) { if (is_prime[i]) { printf("%d ", i); } } printf("\n"); return 0; } 分析与优化 空间优化 ：上述代码中，我们使用了一个布尔数组来标记素数。如果只需要输出素数，而不是存储它们，可以使用位操作来节省空间。 时间优化 ：在上述代码中，我们只遍历到 sqrt(MAX_NUM) ，因为如果一个数不是素数，它必然有一个因子小于或等于它的平方根。 总结 通过本文，我们了解了如何在C语言中使用埃拉托斯特尼筛法高效地求出999以内的所有素数。这种算法不仅简单易懂，而且效率高，适合处理小范围内的素数问题。在实际应用中，我们可以根据具体需求对算法进行优化，以达到最佳性能。