Java如何快速判断素数？

Java素数判断方法详解

素数（质数）指大于1的自然数中，除了1和它本身外无法被其他整数整除的数（如2、3、5、7），在Java中判断素数需结合数学原理和代码优化,以下是完整实现方案：

基础实现原理

1. 试除法：遍历2到n-1的所有整数，检查是否能整除n
2. 边界条件：
   • n ≤ 1 → 非素数
   • n = 2 → 素数（唯一偶素数）
   • n为偶数 → 非素数（2除外）

优化方法（时间复杂度 O(√n)）

数学原理：若n不是素数，必有一个因子≤√n

public static boolean isPrime(int n) {
    if (n <= 1) return false;    // 排除负数、0、1
    if (n == 2) return true;     // 2是素数
    if (n % 2 == 0) return false; // 排除偶数
    // 从3开始，遍历到sqrt(n)，步进+2（跳过偶数）
    for (int i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

完整可运行示例

import java.util.Scanner;
public class PrimeChecker {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("输入整数: ");
        int num = scanner.nextInt();
        if (isPrime(num)) {
            System.out.println(num + " 是素数");
        } else {
            System.out.println(num + " 不是素数");
        }
    }
    // 优化后的素数判断方法
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        // 检查6k±1形式的数（进一步优化）
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

关键优化点

1. 减少循环次数：
   • 只检查到√n（i <= Math.sqrt(n) 或 i * i <= n）
   • 跳过偶数（从3开始，每次+2）
2. 6k±1法则（更高阶优化）：
   • 所有素数（除2、3）都满足 6k±1 形式
   • 循环以5为起点，检查 i 和 i+2（即5,7 → 11,13 → …）

特殊值处理

性能对比

应用场景

1. 密码学（RSA加密）
2. 哈希算法设计
3. 算法题（如查找区间内所有素数）
4. 数学计算库（如Apache Commons Math的Primes类）

注意事项：

• 大整数需用BigInteger.isProbablePrime()（概率算法，适用于加密场景）
• 避免在循环中重复创建对象，批量判断时用筛法（如埃拉托斯特尼筛法）

引用说明：

• 素数定义参考《数论基础》（Hardy著）
• 6k±1优化原理源自GeeksforGeeks算法库
• 性能测试数据基于Oracle JDK 17基准测试
• 密码学应用参照《应用密码学手册》(Menezes著)

通过结合数学定理和代码优化，可在Java中高效判断素数，实际开发建议使用BigInteger类处理超过long范围的大整数,或使用预编译素数表提升重复查询效率。