Java 质数 (prime numbers) 算法实现
一、题目
编写 Java 程序，查找指定范围内的所有质数（素数），质数定义：大于 1，除了 1 和自身，不能被其他自然数整除的整数。
二、质数原理说明
- 质数
n≥2，2 是最小质数，偶数除 2 以外全不是质数； - 优化判断：只需遍历
2 ~ √n，若区间内没有能整除 n 的数，则 n 为质数（因数成对出现，超过平方根无需校验）。
三、Java 代码
public class PrimeDemo { public static void main(String[] args) { // 查找1~100之间所有质数 int max = 100; System.out.println("1~"+max+"之间的质数："); for(int num = 2; num <= max; num++){ if(isPrime(num)){ System.out.print(num + " "); } } } /** * 判断一个数是否为质数 * @param n 待判断数字 * @return 是质数返回true，否则false */ public static boolean isPrime(int n){ if(n < 2){ return false; } // 遍历2到根号n double sqrt = Math.sqrt(n); for(int i = 2; i <= sqrt; i++){ if(n % i == 0){ // 能被整除，不是质数 return false; } } return true; } }四、代码解析
isPrime(int n)工具方法：- 小于 2 直接非质数；
- 循环上限取
√n，大幅减少循环次数，优化性能； - 只要存在约数立刻返回
false，遍历结束无约数返回true。
- main 主方法：循环遍历
2~max，调用判断方法，输出所有质数。
五、运行结果
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 97六、进阶优化思路（博客拓展内容）
- 埃氏筛法（高效批量找质数）：适合超大范围批量筛选，用布尔数组标记合数，速度远优于逐个判断：
// 埃拉托斯特尼筛法示例 public static void sievePrime(int limit){ boolean[] isPrimeArr = new boolean[limit+1]; // 初始默认全部是质数 Arrays.fill(isPrimeArr,true); isPrimeArr[0] = isPrimeArr[1] = false; for(int i=2; i<=Math.sqrt(limit);i++){ if(isPrimeArr[i]){ // i的倍数全部标记为非质数 for(int j=i*i; j<=limit; j+=i){ isPrimeArr[j]=false; } } } // 输出质数 for(int i=2;i<=limit;i++){ if(isPrimeArr[i]) System.out.print(i+" "); } }- 适用场景：小范围用逐个判断法，十万 / 百万级大范围优先埃氏筛。
七、总结
- 基础质数判断核心：平方根优化循环边界，减少冗余运算；
- 两种实现方案：单个数校验、批量筛质数，按需选用；
- 面试常考点：质数算法优化、埃氏筛原理。