求素数是编程入门的经典算法题它不仅能帮助我们巩固循环、条件判断等基础语法还能引导我们思考如何通过算法优化提升程序效率。本文将从最基础的暴力枚举法开始逐步深入到平方根优化法和高效的埃拉托斯特尼筛法带你完整掌握 1~100 素数的求解思路。一、什么是素数素数质数是指大于 1 的自然数且除了 1 和它本身之外不能被其他任何自然数整除的数。例如 2、3、5、7 都是素数而 4能被 2 整除、6能被 2 和 3 整除都不是素数。最小的素数是 2也是唯一的偶素数大于 2 的偶数都不是素数1 既不是素数也不是合数二、方法一基础暴力枚举法核心原理对于每个待判断的数n从 2 到 100依次检查它是否能被 2 到n-1之间的任意整数整除。如果存在能整除的数则n是合数否则n是素数。代码实现public class PrimeNumberBasic {public static void main(String[] args) {System.out.println(“1~100之间的素数暴力法”);int count 0; // 统计素数个数for (int num 2; num 100; num) { boolean isPrime true; // 标记是否为素数 // 检查2到num-1之间的数能否整除num for (int i 2; i num; i) { if (num % i 0) { isPrime false; break; // 找到因数直接退出循环 } } if (isPrime) { System.out.print(num ); count; } } System.out.println(\n1~100之间共有 count 个素数); }}优缺点分析优点逻辑简单直观容易理解适合初学者入门缺点效率极低。例如判断 100 是否为素数时需要循环 98 次对于大数来说这种方法几乎不可用三、方法二平方根优化法优化原理如果一个数n是合数那么它一定可以分解成两个因数a和b即n a × b。其中必有一个因数小于或等于√n另一个大于或等于√n。因此我们只需要检查 2 到√n之间的数即可无需检查到n-1。例如判断 100 是否为素数时只需要检查到 10√10010而不是 99循环次数减少了 90%。代码实现public class PrimeNumberSqrt {public static void main(String[] args) {System.out.println(“1~100之间的素数平方根优化法”);int count 0;for (int num 2; num 100; num) { boolean isPrime true; // 只需要检查到num的平方根 int sqrtNum (int) Math.sqrt(num); for (int i 2; i sqrtNum; i) { if (num % i 0) { isPrime false; break; } } if (isPrime) { System.out.print(num ); count; } } System.out.println(\n1~100之间共有 count 个素数); }}效率对比暴力法判断 100 以内的素数需要循环约 4950 次平方根优化法只需要循环约 300 次效率提升了 16 倍以上数值范围越大优化效果越明显四、方法三埃拉托斯特尼筛法推荐核心原理埃拉托斯特尼筛法简称埃氏筛是批量求范围内素数最高效的算法之一。它的核心思想是先创建一个布尔数组标记所有数为 “素数”初始值为true将 0 和 1 标记为 “非素数”从最小的素数 2 开始将它的所有倍数4、6、8、10…标记为 “非素数”接着处理下一个未被标记的数即下一个素数重复步骤 3最终数组中值为true的索引就是素数代码实现public class PrimeNumberSieve {public static void main(String[] args) {int max 100;// 创建布尔数组索引代表数字值代表是否为素数boolean[] isPrime new boolean[max 1];// 初始化假设所有数都是素数 for (int i 2; i max; i) { isPrime[i] true; } // 埃氏筛核心逻辑 for (int i 2; i * i max; i) { if (isPrime[i]) { // 如果i是素数标记它的所有倍数为非素数 for (int j i * i; j max; j i) { isPrime[j] false; } } } // 输出结果 System.out.println(1~100之间的素数埃氏筛法); int count 0; for (int i 2; i max; i) { if (isPrime[i]) { System.out.print(i ); count; } } System.out.println(\n1~100之间共有 count 个素数); }}为什么这么高效埃氏筛的时间复杂度为O(n log log n)远优于暴力法的O(n²)它通过批量标记合数的方式避免了对每个数进行单独判断对于求 1~10000 甚至更大范围的素数埃氏筛的优势会更加明显五、1~100 的素数完整列表以上三种方法运行后都会得到相同的结果1~100 之间共有 25 个素数2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97六、拓展进一步优化偶素数优化除了 2 之外所有偶数都不是素数。因此可以在循环中只处理奇数将数组大小和循环次数减少一半分段筛法当求非常大范围内的素数如 1~10^9时内存无法容纳整个数组此时可以使用分段筛法将范围分成多个小块分别处理多线程筛法利用多线程并行标记不同素数的倍数进一步提升处理速度适合超大范围七、总结暴力枚举法适合理解素数的基本概念不适合实际开发平方根优化法适合单个大数的素数判断逻辑简单且效率不错埃拉托斯特尼筛法批量求范围内素数的首选方案效率最高