java如何判断质素

判断质数的方法

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

基础方法

通过遍历从2到n-1的所有数，检查是否能整除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;
}

优化方法1

只需要检查到√n即可，因为如果n有因数，必定有一个小于等于√n。

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

优化方法2

跳过偶数，因为除了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 * i <= n; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

使用BigInteger类

Java的BigInteger类提供了isProbablePrime方法，适用于大数判断。

import java.math.BigInteger;

public static boolean isPrime(int n) {
    BigInteger bigInt = BigInteger.valueOf(n);
    return bigInt.isProbablePrime(100); // 参数为确定性，值越高越准确
}

性能比较

• 基础方法适用于小范围的数，但效率较低。
• 优化方法1和2显著提高了性能，尤其是对大数。
• BigInteger.isProbablePrime适用于极大数的快速判断，但有一定概率性。