当前位置：首页 > Java

java 如何判断素数

2026-03-03 18:27:28Java

判断素数的基本方法

素数是大于1的自然数，除了1和它本身外没有其他约数。以下是几种常见的判断方法：

暴力法（试除法）

通过遍历2到n-1的所有整数，检查是否能整除n。若存在能整除的数，则n不是素数。

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

优化试除法

只需检查2到√n的整数，因为若n有约数大于√n，必有一个对应的约数小于√n。

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

进一步优化（跳过偶数）

除2外，所有偶数都不是素数。可以跳过偶数检查，减少循环次数。

public static boolean isPrime(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;
}

适用于大数的概率性测试（Miller-Rabin算法）

对于极大数（如加密场景），确定性方法效率低，可采用概率性测试。以下是一个简化实现：

java 如何判断素数

import java.math.BigInteger;

public static boolean isPrime(BigInteger n, int k) {
    if (n.compareTo(BigInteger.ONE) <= 0) {
        return false;
    }
    if (n.compareTo(BigInteger.valueOf(3)) <= 0) {
        return true;
    }
    if (n.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
        return false;
    }

    BigInteger d = n.subtract(BigInteger.ONE);
    int s = 0;
    while (d.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
        d = d.divide(BigInteger.TWO);
        s++;
    }

    for (int i = 0; i < k; i++) {
        BigInteger a = randomBigInteger(BigInteger.TWO, n.subtract(BigInteger.TWO));
        BigInteger x = a.modPow(d, n);
        if (x.equals(BigInteger.ONE) || x.equals(n.subtract(BigInteger.ONE))) {
            continue;
        }
        boolean isComposite = true;
        for (int j = 0; j < s - 1; j++) {
            x = x.modPow(BigInteger.TWO, n);
            if (x.equals(n.subtract(BigInteger.ONE))) {
                isComposite = false;
                break;
            }
        }
        if (isComposite) {
            return false;
        }
    }
    return true;
}

private static BigInteger randomBigInteger(BigInteger min, BigInteger max) {
    BigInteger range = max.subtract(min).add(BigInteger.ONE);
    BigInteger res;
    do {
        res = new BigInteger(range.bitLength(), new java.util.Random());
    } while (res.compareTo(range) >= 0);
    return res.add(min);
}