Java 中如何使用函数判断是否为质数

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

方法二：优化判断

在方法一中，我们遍历了2到N-1的所有整数来判断是否能被整除，这样的话时间复杂度为O(N)。但其实我们只需要遍历2到√N的整数即可，因为如果整数N不是质数，那么一定可以找到一个小于或等于√N的整数整除它。代码如下：

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;
    }
    
    boolean[] isComposite = new boolean[n + 1];
    isComposite[0] = true;
    isComposite[1] = true;
    
    for (int i = 2; i * i <= n; i++) {
        if (!isComposite[i]) {
            for (int j = i * i; j <= n; j += i) {
                isComposite[j] = true;
            }
        }
    }
    
    return !isComposite[n];
}

这三种方法中，方法一是最简单直接的暴力判断方法，方法二是对暴力判断的优化，而方法三则是一种更高效的筛法。根据需求和数据量的大小，选择适合的方法来判断质数。