1. 什么是素数素数又称质数是指大于 1的自然数中除了 1 和它本身以外不再有其他因数的数。例如 2、3、5、7、11 都是素数而 4、6、8、9 都不是素数。判断一个数是否为素数是 C 语言初学者最经典的练习题目之一也是后续学习算法优化、数论的基础。2. 最基础的判断方法最直观的思路对于一个数n从 2 开始一直试除到n-1如果中间存在某个数能整除n则n不是素数否则n是素数。#includestdio.hintisPrime(intn){if(n1){return0;// 1 和负数不是素数}for(inti2;in;i){if(n%i0){return0;// 能被整除不是素数}}return1;// 是素数}intmain(){intnum;printf(请输入一个整数);scanf(%d,num);if(isPrime(num)){printf(%d 是素数\n,num);}else{printf(%d 不是素数\n,num);}return0;}这种方法虽然正确但效率较低。当n很大时循环次数接近n次时间复杂度为 O(n)。3. 优化一只需判断到 √n观察可以发现如果n有一个大于√n的因数a那么必然存在一个小于√n的因数b n / a。因此我们只需要从 2 试除到√n即可。#includestdio.h#includemath.hintisPrime(intn){if(n1){return0;}for(inti2;isqrt(n);i){if(n%i0){return0;}}return1;}这样时间复杂度降为 O(√n)性能大幅提升。4. 优化二跳过偶数除了 2 以外所有偶数都不是素数。因此可以先单独判断 2然后从 3 开始只检查奇数。intisPrime(intn){if(n1){return0;}if(n2){return1;// 2 是素数}if(n%20){return0;// 偶数不是素数}for(inti3;isqrt(n);i2){if(n%i0){return0;}}return1;}这样循环次数又减少了一半效率进一步提升。5. 综合示例输出 1~100 之间的所有素数下面把上面的优化综合起来输出 1 到 100 之间的所有素数#includestdio.h#includemath.hintisPrime(intn){if(n1){return0;}if(n2){return1;}if(n%20){return0;}for(inti3;isqrt(n);i2){if(n%i0){return0;}}return1;}intmain(){printf(1~100 之间的素数有\n);for(inti1;i100;i){if(isPrime(i)){printf(%d ,i);}}printf(\n);return0;}运行结果1~100 之间的素数有 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 976. 进阶埃拉托斯特尼筛法当需要一次性判断大量数字比如求 1 到 1000000 之间所有素数时逐个判断效率太低。此时可以使用埃拉托斯特尼筛法Sieve of Eratosthenes时间复杂度为 O(n log log n)。基本思想从 2 开始把每个素数的倍数都标记为合数剩下的就是素数。#includestdio.h#includestdbool.hvoidsieve(intn){bool isPrime[n1];for(inti0;in;i){isPrime[i]true;}isPrime[0]isPrime[1]false;for(inti2;i*in;i){if(isPrime[i]){for(intji*i;jn;ji){isPrime[j]false;}}}printf(1~%d 之间的素数有\n,n);for(inti2;in;i){if(isPrime[i]){printf(%d ,i);}}printf(\n);}intmain(){sieve(100);return0;}7. 总结方法时间复杂度适用场景基础试除法O(n)小数字、教学演示试除到 √nO(√n)单个数字判断跳过偶数优化O(√n/2)单个数字判断推荐埃拉托斯特尼筛法O(n log log n)批量判断大量数字掌握素数的判断方法不仅能帮助你通过 C 语言的基础练习更是理解算法复杂度优化的重要一步。建议初学者先掌握基础写法再逐步理解优化思路最后尝试用筛法解决更大规模的问题。