当前位置：首页 > Java

如何判断素数java

2026-03-25 08:06:16Java

判断素数的 Java 方法

素数是指大于1的自然数，且只能被1和它本身整除的数。以下是几种在 Java 中判断素数的方法。

方法一：基础判断法

从2到n-1逐个检查是否能整除n，如果存在能整除的数，则n不是素数。

如何判断素数java

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

方法二：优化检查范围

检查范围可以缩小到√n，因为如果n能被大于√n的数整除，那么它必然也能被小于√n的数整除。

如何判断素数java

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 算法

对于大数判断，Miller-Rabin 算法是一种概率性测试方法，效率更高。

import java.math.BigInteger;

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

使用示例

public class Main {
    public static void main(String[] args) {
        int num = 29;
        if (isPrime(num)) {
            System.out.println(num + " 是素数");
        } else {
            System.out.println(num + " 不是素数");
        }
    }

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