当前位置：首页 > Java

java如何实现质数

2026-03-23 01:15:56Java

判断质数的基本方法

质数是指大于1的自然数，除了1和它本身外没有其他约数。以下是一个简单的Java实现方法：

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

优化方法：筛法（埃拉托斯特尼筛法）

如果需要生成一定范围内的所有质数，可以使用筛法提高效率：

public static List<Integer> sieveOfEratosthenes(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }
    return primes;
}

大数质数检测（Miller-Rabin算法）

对于非常大的数（如超过int范围），可以使用概率性算法如Miller-Rabin进行高效检测：

java如何实现质数

import java.math.BigInteger;

public static boolean isPrimeMillerRabin(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 composite = true;
        for (int j = 0; j < s - 1; j++) {
            x = x.modPow(BigInteger.TWO, n);
            if (x.equals(n.subtract(BigInteger.ONE))) {
                composite = false;
                break;
            }
        }
        if (composite) {
            return false;
        }
    }
    return true;
}

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