5种Java判断素数的实现方法与性能深度解析

admin 2025-07-01 阅读:8 评论:0

在编程面试和算法实践中，素数判断是一个经典问题。本文将深入探讨Java中判断素数的多种方法，并分析它们的性能差异，帮助开发者选择最适合不同场景的解决方案。一、什么是素数？素数(质数)是指在大于1的自然数中，除了1和它本身以外不再有其他因数...

在编程面试和算法实践中，素数判断是一个经典问题。本文将深入探讨Java中判断素数的多种方法，并分析它们的性能差异，帮助开发者选择最适合不同场景的解决方案。

一、什么是素数？

素数(质数)是指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。比如2、3、5、7等都是素数，而4、6、8等则不是。

二、基础判断方法

1. 暴力法

这是最直观的判断方法：

5种Java判断素数的实现方法与性能深度解析

public static boolean isPrimeBasic(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

时间复杂度：O(n)

2. 优化边界法

观察到只需要检查到√n即可：

5种Java判断素数的实现方法与性能深度解析

public static boolean isPrimeSqrt(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

时间复杂度：O(√n)

三、进阶优化方法

3. 排除偶数法

除了2，所有偶数都不是素数：

public static boolean isPrimeEven(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

4. 6k±1优化法

所有大于3的素数都可以表示为6k±1的形式：

5种Java判断素数的实现方法与性能深度解析

public static boolean isPrime6k(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

四、专业级解决方案

5. 米勒-拉宾素性测试

对于非常大的数，可以使用概率算法：

public static boolean isPrimeMillerRabin(int n, int k) {
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;

    int d = n - 1;
    while (d % 2 == 0) d /= 2;

    for (int i = 0; i < k; i++) {
        if (!millerTest(d, n)) return false;
    }
    return true;
}

private static boolean millerTest(int d, int n) {
    int a = 2 + (int)(Math.random() % (n - 4));
    int x = modPow(a, d, n);
    if (x == 1 || x == n - 1) return true;

    while (d != n - 1) {
        x = (x * x) % n;
        d *= 2;
        if (x == 1) return false;
        if (x == n - 1) return true;
    }
    return false;
}