java如何表示质数

判断质数的方法

质数是指大于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;
}

优化质数判断

对于较大的数，可以采用更高效的算法如Miller-Rabin素性测试：

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;
}

private static int modPow(int a, int d, int n) {
    int res = 1;
    a = a % n;
    while (d > 0) {
        if ((d & 1) == 1) {
            res = (res * a) % n;
        }
        d = d >> 1;
        a = (a * a) % n;
    }
    return res;
}

生成质数列表

生成指定范围内的所有质数可以使用埃拉托斯特尼筛法：

public static List<Integer> sieveOfEratosthenes(int n) {
    boolean[] prime = new boolean[n + 1];
    Arrays.fill(prime, true);
    prime[0] = false;
    prime[1] = false;

    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }

    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            primes.add(i);
        }
    }
    return primes;
}

使用BigInteger类

对于非常大的质数，可以使用Java的BigInteger类：

import java.math.BigInteger;

public static boolean isBigPrime(BigInteger num) {
    return num.isProbablePrime(100); // 确定性参数
}

这些方法覆盖了从基本质数判断到处理大质数的各种场景，可以根据具体需求选择合适的方法。