Java中生成质数的方法 | Baeldung中文网

1. 引言

本文将介绍多种在Java中生成质数的高效方法。如果你需要判断单个数字是否为质数，可以参考这篇快速指南。

2. 质数定义

质数是指大于1的自然数，除了1和它本身外没有其他正因数。

例如：

✅ 7是质数（仅能被1和7整除）
❌ 12不是质数（能被1,2,3,4,6,12整除）

3. 生成质数的方法

3.1 Java 7及之前版本——暴力法

public static List<Integer> primeNumbersBruteForce(int n) {
    List<Integer> primeNumbers = new LinkedList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrimeBruteForce(i)) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}
public static boolean isPrimeBruteForce(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

这个方法的核心逻辑：

遍历2到n的所有数字
对每个数字调用isPrimeBruteForce()检查是否为质数
检查方法通过测试从2到number-1的所有除数
⚠️ 一旦发现可整除的数立即返回false
最终通过所有测试则返回true

3.2 效率优化

暴力法的时间复杂度是O(n²)，显然有优化空间。关键改进点：

平方根优化：
若number = a × b，则a和b至少有一个≤√number。因此只需检查到√number即可。
跳过偶数：
除了2，所有偶数都不是质数。

优化后的代码：

public static List<Integer> primeNumbersBruteForce(int n) {
    List<Integer> primeNumbers = new LinkedList<>();
    if (n >= 2) {
        primeNumbers.add(2);
    }
    for (int i = 3; i <= n; i += 2) {
        if (isPrimeBruteForce(i)) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}
private static boolean isPrimeBruteForce(int number) {
    for (int i = 2; i*i <= number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

3.3 Java 8实现

用Java 8的流式API重写：

public static List<Integer> primeNumbersTill(int n) {
    return IntStream.rangeClosed(2, n)
      .filter(x -> isPrime(x)).boxed()
      .collect(Collectors.toList());
}
private static boolean isPrime(int number) {
    return IntStream.rangeClosed(2, (int) (Math.sqrt(number)))
      .allMatch(n -> x % n != 0);
}

核心改进：

使用IntStream生成数字序列
通过allMatch确保无整除因子
自动装箱为Integer集合

3.4 埃拉托斯特尼筛法

更高效的算法，时间复杂度O(n logn)：

public static List<Integer> sieveOfEratosthenes(int n) {
    boolean prime[] = new boolean[n + 1];
    Arrays.fill(prime, true);
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
    List<Integer> primeNumbers = new LinkedList<>();
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}

算法步骤：

创建2到n的布尔数组，初始全为true
从p=2开始：
- 若prime[p]为true，标记所有p的倍数为false
找到下一个未标记的数作为新p
重复直到p² > n
剩余true值对应的索引即为质数

3.5 筛法工作示例（n=30）

算法执行过程：

🔴 p=2：标记所有2的倍数（4,6,8,...）
🟢 p=3：标记所有3的倍数（6,9,12,...）
p=4：已标记，跳过
🟣 p=5：标记所有5的倍数（10,15,20,...）
持续到p>√30（约5.4）

最终未标记的数字：2,3,5,7,11,13,17,19,23,29

4. 结论

本文展示了四种生成质数的方法：

暴力法（基础但低效）
优化暴力法（平方根+跳过偶数）
Java 8流式实现（简洁优雅）
埃拉托斯特尼筛法（最高效）

完整代码示例可在GitHub仓库获取。根据实际场景选择合适算法——小范围用优化暴力法，大范围强烈推荐筛法。

Persistence

REST

Security