Java判断一个数是否为素数

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

Miller-Rabin素性测试（适用于大数）

import java.util.Random;
public static boolean isPrimeMillerRabin(int num, int k) {
    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++;
    }
    // 进行k次测试
    Random random = new Random();
    for (int i = 0; i < k; i++) {
        int a = 2 + random.nextInt(num - 4);
        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 + " 是素数吗? " + isPrime(number));
        System.out.println(number + " 是素数吗(优化方法)? " + isPrimeOptimized(number));
        System.out.println(number + " 是素数吗(Miller-Rabin)? " + isPrimeMillerRabin(number, 5));
    }
}

方法比较

1. 简单试除法：适用于小数字，简单直观但效率较低
2. 优化试除法：跳过偶数，效率比简单方法高
3. Miller-Rabin测试：适用于大数字，是概率性算法，可以通过增加测试次数提高准确性

对于大多数实际应用场景，优化后的试除法已经足够高效，如果需要处理非常大的数字（如超过64位整数），可以考虑使用Miller-Rabin测试或专门的素性测试算法。