当前位置：首页 > news >正文

Java 质数 (prime numbers) 算法实现

news 2026/6/5 21:16:36

一、题目

编写 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+" "); } }