1. 从一道经典习题说起为什么是素数如果你刚开始学习C语言或者正在刷一些编程练习题那么“输出1-100之间的素数”这道题你大概率会遇到。它就像编程路上的一个“新手村守门员”看似简单却能把很多初学者卡住。题目本身不复杂但背后考察的知识点却很扎实循环嵌套、条件判断、算法优化甚至是对计算机“计算”这件事最朴素的理解。很多人拿到题目第一反应可能是“素数不就是只能被1和它本身整除的数吗那我从2到100每个数都拿比它小的数除一遍看看能不能整除不就行了”这个思路完全正确也是我们最直观的“暴力枚举法”。但如果你真这么写代码可能会又慢又啰嗦。这道题的魅力就在于它有好几种解法从最笨的到最高效的清晰地展示了编程思维从“实现功能”到“追求效率”的进化过程。在开始敲代码之前我们先明确一下“素数”的定义一个大于1的自然数除了1和它自身外不能被其他自然数整除的数。2是最小的素数也是唯一的偶素数。1不是素数这是一个关键边界条件写代码时千万别忘了。接下来我将带你用三种不同的方法来实现这个功能。这三种方法难度递增思维深度也递增。第一种方法帮你巩固基础语法第二种方法引入关键的优化思想第三种方法则会让你接触到一点“空间换时间”的算法策略。无论你是刚学完循环的萌新还是想复习一下基础算法的朋友相信都能从中获得启发。2. 方法一最直接的“试除法”这是最符合人类直觉的解法我们称之为“试除法”或“暴力枚举法”。其核心思想是对于每一个待判断的数n我们用所有可能的除数从2到n-1去尝试整除它。如果发现任何一个数能整除n那么n就不是素数如果遍历完所有可能的除数都没有找到能整除的那么n就是素数。2.1 代码实现与逐行解析我们先来看代码然后一步步拆解。#include stdio.h int main() { int i, j, isPrime; printf(1-100之间的素数有\n); // 外层循环遍历1-100之间的每一个数 for (i 2; i 100; i) { isPrime 1; // 先假设当前数i是素数标记为1真 // 内层循环用2到i-1之间的每一个数j去试除i for (j 2; j i; j) { if (i % j 0) { // 如果i能被j整除 isPrime 0; // 那么i不是素数标记改为0假 break; // 已经确定不是素数立即跳出内层循环无需继续尝试 } } // 根据isPrime标志的值决定是否输出i if (isPrime 1) { printf(%d , i); } } printf(\n); return 0; }代码解析与关键点变量定义i用于遍历1-100j作为可能的除数isPrime是一个“标志变量”用于记录当前数i是否为素数的状态。这是一个非常重要的编程技巧用变量来记录某种状态比在循环里直接判断要清晰得多。外层循环 (for (i 2; ...))注意我们从i2开始。因为1不是素数直接从2开始判断这避免了额外的条件判断。初始化标志 (isPrime 1)在判断每一个新的数i之前我们都先“乐观地”假设它是素数。这是一种常见的初始化逻辑。内层循环 (for (j 2; j i; j))这是算法的核心。我们用j从2开始一直试到i-1。i % j是取模运算计算i除以j的余数。if (i % j 0)如果余数为0意味着j能整除ii就不是素数。一旦发现i不是素数我们立即做两件事将isPrime标志设为0使用break语句跳出内层循环。break在这里非常关键它能避免无谓的后续计算。比如判断4是不是素数当j2时就已经发现它能被整除就没必要再去试j3了。输出判断 (if (isPrime 1))内层循环结束后检查标志。如果标志仍然是1说明在2到i-1之间没有找到能整除i的数那么i就是素数将其输出。2.2 方法一的优缺点与思考优点逻辑极其清晰完全贴合素数的定义最容易理解和实现。巩固基础完美地练习了for循环嵌套、if条件判断、break语句以及标志变量的使用。缺点效率低下这是最大的问题。为了判断一个数n是否为素数最坏情况下需要进行n-2次取模运算即内层循环接近n次。当n很大时比如判断一个10亿级别的数这个算法慢得无法接受。即使对于100以内的数它也做了很多不必要的计算。实操心得很多初学者在这里容易忘记break导致即使已经知道不是素数程序还会傻傻地继续试除直到循环结束。虽然对结果没影响标志最终会被设为0但浪费了计算资源。记住在确定结果后及时“刹车”是一个好习惯。虽然效率低但方法一是所有优化的基础。接下来我们看看如何让它变得聪明一点。3. 方法二优化试除范围试除到 sqrt(i)方法一慢是因为它“试”得太多了。我们真的需要试除到i-1吗仔细想想数学原理其实不需要。核心优化思想如果n不是素数那么它一定可以表示成两个因数的乘积n a * b。其中a和b不可能都大于n的平方根。反证一下如果a和b都大于sqrt(n)那么a * b sqrt(n) * sqrt(n) n这与a * b n矛盾。因此在a和b中至少有一个小于或等于sqrt(n)。这意味着什么这意味着我们在寻找n的因数时只需要找到那个较小的因数就行了。而这个较小的因数一定在2到sqrt(n)之间。如果在2到sqrt(n)之间都找不到能整除n的数那么在sqrt(n)到n-1之间也绝对找不到。因为如果sqrt(n)到n-1之间有一个因数那么必然对应一个2到sqrt(n)之间的另一个因数。结论判断n是否为素数只需要用2到sqrt(n)之间的数去试除即可。3.1 代码实现引入数学库与循环优化#include stdio.h #include math.h // 引入数学库用于计算平方根sqrt() int main() { int i, j, isPrime; printf(1-100之间的素数有\n); for (i 2; i 100; i) { isPrime 1; // 关键优化内层循环的上界改为 j sqrt(i) // 注意sqrt()函数参数和返回值都是double类型这里与int比较编译器会做隐式转换 // 更严谨的写法是 j (int)sqrt(i)但针对i100直接比较问题不大 for (j 2; j sqrt(i); j) { if (i % j 0) { isPrime 0; break; } } if (isPrime 1) { printf(%d , i); } } printf(\n); return 0; }代码变化与解析#include math.h因为使用了sqrt()函数来计算平方根所以需要包含数学头文件。在编译时可能需要加上-lm参数来链接数学库例如在Linux GCC下gcc prime.c -o prime -lm。内层循环条件 (j sqrt(i))这是性能提升的关键。对于每个数i内层循环的次数从大约i次锐减到大约sqrt(i)次。当i100时原来要试除98次现在只需要试除到10最多10次。效率提升是指数级的。类型注意sqrt(i)返回的是double类型双精度浮点数而j是int。在j sqrt(i)这个比较中j会被自动转换为double类型进行比较。对于小范围整数这没有问题。更精确的写法是j (int)sqrt(i)或者为了避免浮点数误差使用j * j i作为循环条件这甚至是更推荐的写法。3.2 进一步优化跳过偶数我们还可以进行一个非常直观的优化除了2以外所有的偶数都不可能是素数因为它们至少能被2整除。所以在外层循环中我们可以跳过所有大于2的偶数。#include stdio.h #include math.h int main() { int i, j, isPrime; printf(1-100之间的素数有\n); printf(2 ); // 单独处理2它是唯一的偶素数 // 外层循环从3开始每次加2这样就只遍历奇数 for (i 3; i 100; i 2) { isPrime 1; // 内层循环依然试除到 sqrt(i) for (j 2; j sqrt(i); j) { if (i % j 0) { isPrime 0; break; } } if (isPrime 1) { printf(%d , i); } } printf(\n); return 0; }这个优化带来的好处外层循环次数减半。原来要遍历99个数2-100现在只需要遍历50个奇数3,5,7,...,99再加上单独处理的2。因为需要判断的数少了一半整体计算量也相应大幅下降。注意事项这个优化建立在“偶数不是素数除了2”这个简单事实之上非常有效。但它也提醒我们在优化时首先要从算法逻辑本身寻找“捷径”而不是一味追求代码的微观优化。3.3 方法二的总结方法二通过“缩小试除范围”和“跳过偶数”将算法效率提升了好几个数量级。对于求解1-100以内的素数这已经绰绰有余甚至有点“杀鸡用牛刀”的感觉。但它的意义在于展示了算法思维通过数学洞察力减少不必要的计算。这是从“正确编程”走向“高效编程”的重要一步。然而如果我们不是求100以内而是求100万甚至1000万以内的所有素数呢方法二可能还是会有点慢因为对于每个数我们仍然需要进行多次取模运算尽管次数少了很多。有没有一种方法能“批量”地标记出素数而不是一个个独立判断4. 方法三埃拉托斯特尼筛法Sieve of Eratosthenes这是一种古老而高效的算法用于找出一定范围内所有的素数。它的思路不再是“判断每个数是不是素数”而是“筛掉所有不是素数的数”剩下的就是素数。就像一个筛子把合数非素数筛掉。4.1 算法原理与步骤假设我们要找出n以内的所有素数。创建筛子创建一个大小为n1的布尔数组isPrime[]初始化所有元素为true表示我们先假设所有数都是素数。通常我们忽略isPrime[0]和isPrime[1]因为0和1不是素数。开始筛选从第一个素数2开始。将2标记为素数保持isPrime[2] true。然后将2的所有倍数4, 6, 8, 10, ...标记为非素数isPrime[4] false,isPrime[6] false, ...。因为这些数都能被2整除所以它们一定是合数。寻找下一个素数在数组中找到下一个未被标记为false的数即仍是true的数。这个数一定是素数为什么因为所有小于它的素数的倍数都已经被筛掉了如果它不是素数它应该已经被某个更小的素数筛掉了。对于n100下一个是3。重复步骤2将3标记为素数然后将3的所有倍数6, 9, 12, 15, ...标记为非素数。注意像6、12这些既是2的倍数又是3的倍数的数会被重复标记但这不影响结果。循环继续重复这个过程直到我们找到的素数的平方大于n为止。为什么因为对于任意一个合数m它一定有一个不大于sqrt(m)的质因数。当我们用所有小于等于sqrt(n)的素数去筛过后n以内的所有合数都已经被筛掉了。对于n100我们只需要用小于等于10的素数2,3,5,7去筛即可。输出结果遍历isPrime数组所有值为true的下标就是素数。4.2 代码实现用数组模拟筛子#include stdio.h #include stdbool.h // 使用bool类型需要这个头文件C99标准 #define MAX_N 100 // 定义查找范围的上限 int main() { // 创建一个布尔数组isPrime[i]为true表示i是素数 bool isPrime[MAX_N 1]; // 1. 初始化数组假设所有数都是素数 for (int i 0; i MAX_N; i) { isPrime[i] true; } // 0和1不是素数手动设置为false isPrime[0] false; isPrime[1] false; // 2. 埃拉托斯特尼筛法核心过程 for (int i 2; i * i MAX_N; i) { // 只需遍历到 sqrt(MAX_N) if (isPrime[i] true) { // 如果i是素数则将其所有倍数标记为非素数 // 从 i*i 开始标记因为比 i*i 小的 i 的倍数如 i*2, i*3, ..., i*(i-1) // 已经被比 i 更小的素数标记过了 for (int j i * i; j MAX_N; j i) { isPrime[j] false; } } } // 3. 输出所有素数 printf(1-%d之间的素数有\n, MAX_N); int count 0; for (int i 2; i MAX_N; i) { if (isPrime[i]) { printf(%d , i); count; // 每输出10个素数换一行让输出更美观 if (count % 10 0) { printf(\n); } } } printf(\n共计 %d 个素数。\n, count); return 0; }代码关键点解析#include stdbool.h和bool类型C语言标准库提供了布尔类型true和false是预定义的常量使代码意图更清晰。如果你的编译器不支持C99可以用int数组用1和0代替。#define MAX_N 100使用宏定义上限方便修改查找范围。外层循环条件 (i * i MAX_N)这是算法的精髓之一。我们只需要用i遍历到sqrt(MAX_N)。原因前面解释过所有合数都有一个不大于其平方根的质因数。内层循环的起始点 (j i * i)这是另一个重要优化。为什么从i*i开始筛考虑素数i5。它的倍数有10(5*2),15(5*3),20(5*4),25(5*5),30(5*6)... 注意10是2的倍数早在i2时就被筛掉了。15是3的倍数在i3时被筛掉了。20是2的倍数也被筛过了。所以对于素数i所有小于i*i的i的倍数都已经被比i更小的素数筛过了。从i*i开始筛可以避免大量重复操作。内层循环的步长 (j i)j i意味着每次增加i这样就能遍历i的所有倍数。4.3 筛法的性能与内存考量优点效率极高对于生成一个较大范围内的所有素数筛法的时间复杂度接近线性O(n log log n)远高于逐个判断的试除法。当n很大时比如百万、千万级别筛法的优势是压倒性的。思路巧妙它体现了计算机科学中“用空间换时间”和“预处理”的思想。我们通过一个数组空间提前计算并存储了所有数的素数状态之后查询任意一个数是否为素数几乎是瞬间完成的O(1)。缺点需要额外内存需要开辟一个大小为n1的数组。当n极大时例如10亿这个数组会占用大量内存约1GB可能超出限制。而试除法几乎不需要额外空间。结果依赖范围你必须预先知道范围n。如果你只想知道一个特定的数是不是素数用筛法先筛出整个范围就显得很浪费此时优化后的试除法方法二更合适。实操心得与常见坑点数组越界数组大小是MAX_N 1循环时务必注意边界是i MAX_N否则会访问非法内存。重复筛选内层循环从j i * i开始是标准写法。如果写成从j i * 2开始功能正确但会做大量重复工作降低效率。输出格式当素数很多时全部打印在一行会非常混乱。像代码中那样每输出固定个数如10个就换行或者每行固定宽度会让结果清晰很多。统计个数也是一个好习惯。理解“筛”的过程可以尝试在纸上模拟n30时筛法的执行过程一步步看数组isPrime的变化这对理解算法大有裨益。5. 三种方法的对比与选择现在我们把三种方法放在一起从多个维度进行对比这样你就能清楚地知道在什么情况下该用什么方法。特性维度方法一基础试除法方法二优化试除法方法三埃拉托斯特尼筛法核心思想逐个判断试除所有可能因数。逐个判断但利用数学原理大幅减少试除范围。批量筛选标记合数剩下的就是素数。时间复杂度约 O(n²)最慢。约 O(n√n)中等。约 O(n log log n)最快对于求范围内所有素数。空间复杂度O(1)仅需几个变量。O(1)仅需几个变量。O(n)需要与范围n成正比的数组。代码复杂度最简单最直观。中等需理解平方根优化和偶数优化。较高需理解筛法原理和双重循环的起止条件。适用场景学习循环和判断的基础练习范围极小如n1000。判断单个较大数是否为素数或中等范围内如n10^6求所有素数。需要高效获取一个较大范围内所有素数的经典场景如n在10^5到10^7量级。优点逻辑直白易于实现和调试。效率显著高于方法一无需额外空间。区间内求素数效率最高查询O(1)。缺点效率极低n稍大即不可用。对于求区间内所有素数仍需要重复计算。需要较多内存且必须预先确定范围。如何选择如果你是初学者务必从方法一开始亲手实现一遍。它帮你打通“问题-逻辑-代码”的整个流程巩固最基础的语法。理解了方法一再看方法二的优化你会更有感触。如果你需要判断“单个”数是否为素数比如解决“判断一个输入的数是不是素数”这类问题方法二优化试除法是最常用、最合适的选择。它又快又省内存。如果你需要列出“一个区间内”的所有素数比如本题的“输出1-100之间的素数”或者更一般的“输出1-n之间的素数”当n比较大时比如超过1万方法三筛法是毋庸置疑的最佳选择。虽然在n100时它有点大材小用但掌握这个算法对未来解决更复杂问题至关重要。6. 举一反三从习题到实际应用这道题绝不仅仅是一道练习题。理解了求素数的算法你可以解锁很多相关的编程挑战和实际应用场景。1. 孪生素数问题找出一定范围内的所有孪生素数对即相差2的素数对如(3,5), (5,7), (11,13)。你可以先用筛法生成素数数组然后遍历数组检查isPrime[i]和isPrime[i2]是否同时为真。2. 哥德巴赫猜想验证验证一个大偶数是否可以写成两个素数之和。对于给定的偶数n遍历所有小于n的素数p检查n-p是否也是素数。筛法生成的素数表在这里又能派上大用场。3. 素数在密码学中的应用现代密码学如RSA加密算法的核心基础之一就是大素数的难以分解性。虽然实际用的素数非常大几百位但其判断原理如Miller-Rabin概率素性测试是优化试除法的更高级演进。理解基础试除法是学习这些高级算法第一步。4. 算法竞赛中的常见变体很多在线判题系统OJ都有素数相关的题目它们往往不是直接让你输出素数而是将素数判断作为一个子步骤。例如计算一个数的所有质因数、求一个区间内每个数的质因数个数等等。熟练掌握筛法经常能让你在面对这类问题时游刃有余。在我自己最初学习时也曾满足于写出方法一就万事大吉。直到有一次遇到一个需要判断十万级别数据的问题程序跑了半天没结果才被迫去学习更优的算法。当你从“能运行”到“跑得快”这个阶段迈进时对算法和数据结构的理解就会深刻得多。这道关于素数的题目就是一个绝佳的起点。
