Java判断一个数是否为素数

素数（质数）是指大于1的自然数，除了1和它本身外，不能被其他自然数整除的数，以下是几种在Java中判断一个数是否为素数的方法：

方法1：简单试除法

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

方法2：优化试除法（跳过偶数）

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

方法3：Miller-Rabin素性测试（适用于大数）

import java.math.BigInteger;
import java.util.Random;
public static boolean isPrimeMillerRabin(int num, int iterations) {
    if (num <= 1) {
        return false;
    }
    if (num <= 3) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    // 将num-1表示为d*2^s
    int d = num - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }
    Random rand = new Random();
    for (int i = 0; i < iterations; i++) {
        int a = 2 + rand.nextInt(num - 3);
        int x = (int) Math.pow(a, d) % num;
        if (x == 1 || x == num - 1) {
            continue;
        }
        boolean composite = true;
        for (int j = 0; j < s - 1; j++) {
            x = (int) Math.pow(x, 2) % num;
            if (x == num - 1) {
                composite = false;
                break;
            }
        }
        if (composite) {
            return false;
        }
    }
    return true;
}

使用示例

public class PrimeNumberChecker {
    public static void main(String[] args) {
        int number = 17;
        // 使用简单方法
        System.out.println(number + " is prime? " + isPrime(number));
        // 使用优化方法
        System.out.println(number + " is prime? " + isPrimeOptimized(number));
        // 使用Miller-Rabin方法
        System.out.println(number + " is prime? " + isPrimeMillerRabin(number, 5));
    }
    // 这里插入上面的isPrime方法
}

性能比较

1. 简单试除法：适用于小数字，时间复杂度O(√n)
2. 优化试除法：跳过偶数，性能提升约2倍
3. Miller-Rabin测试：适用于大数字，是概率性算法，但可以通过增加迭代次数提高准确性

对于大多数应用场景,优化后的试除法已经足够高效，如果需要处理非常大的数字（如超过64位），建议使用BigInteger和Miller-Rabin测试。