Java函数编写：如何检查一个数是否为质数？

一个数是否为质数是一道经典的算法问题，通常是初学编程的学生们的第一个作业。在这里，我们将介绍几种不同的方法来检查一个数是否为质数，务求帮助初学者更好地理解。

方法一：暴力枚举

暴力枚举方法是最简单和直接的检查一个数是否为质数的方法。其思路就是检查所给定的数对于每一个比它小的数是否有因子。如果存在因子，其就不是质数，否则则为质数。

下面是基于暴力枚举的Java函数实现：

public static boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

该函数中，我们首先判断输入的数是否小于2，如果是，则直接返回false。这是因为质数定义为大于等于2的自然数。然后我们从2开始枚举到n的平方根，判断是否有因子。如果存在因子则说明n不是质数，返回false；如果都不存在，则n为质数，返回true。

该方法最大的缺点是在检查大数时表现极为低效，因为其时间复杂度为O(n)，而且该方法还不能够通过大数据测试。

方法二：优化的暴力枚举

为了提升暴力枚举的效率，我们可以进行一些简单的优化，如只枚举奇数，因为偶数都能被2整除。我们只需要排除2就可以缩小判断范围。此外，我们还可以通过对过去的质数列表进行较小因子的判断，来加速搜索。

下面是代码实现:

public static boolean isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

在该函数中，我们将2作为特殊情况来处理，只检查大于等于3的奇数。此外，我们通过判断过去所有的质数的较小因子来优化搜索过程。

虽然该方法比直接暴力枚举略优，但是对于大数，依旧会导致较差的性能。

方法三：分解质因数

分解质因数是一种较好的方法，既可以检查质数，又可以输出一个数的所以的质因数。这里我们只考虑检查质数，具体实现思路如下：

对于给定的数n，如果存在一个小于1并且大于n的正整数d，那么n除以d的结果一定小于n且大于1，并且n除以d的商和余数分别是q和r，其中0 ≤ r < d。因此n就不能是质数。

根据这个思路，我们可以通过分解n的质因数来检查n是否是质数。如果n有大于sqrt(n)的因子，则一定有小于sqrt(n)的因子。

下面是代码实现：

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

在该函数中，我们将n的因子枚举到sqrt(n)，大于sqrt(n)的因子可以从小于sqrt(n)的因子中推导得出。

该方法的效率比简单的暴力枚举和优化的暴力枚举方法都优秀，但是其空间开销较大。因为分解n的质因数需要存储质数列表。

方法四：埃氏筛法

埃氏筛法是一种在指定区间内，通过不断的筛选质数，来输出输入区间中所有质数的高效算法。该方法适用于求解大量小于一个正整数n的质数。

在实现上，我们从2开始，将小于n的所有正整数标记为素数，然后依次遍历素数列表的每一个元素，将素数的倍数标记为合数。遍历结束后，剩下的未被标记为合数的数即为质数。

下面是基于埃氏筛法的Java实现：

public static List<Integer> sieve(int n) {
    List<Integer> primes = new ArrayList<>();
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }
    return primes;
}

在该代码中，isPrime是一个数组，表示区间小于等于n的数是否是质数，初始所有元素都被认为是质数。如果一个元素是质数，则将其倍数标记为非质数。最后，所有未被标记为非质数的数即为质数。

该方法在处理小于10000的范围内，使用o(n log log n)的时间复杂度仍然是比较快的。但当n较大时，这个方法不再稳定表现，因为isPrime数组需要的空间和n成正比。

方法五：米勒-拉宾算法

毫不夸张的说，米勒-拉宾算法（Miller-Rabin primality test）是一个广泛被使用的判断质数的算法，尤其对于大数的判断具有很强的优势。

米勒-拉宾算法的基本思路是：对于一个正整数n，如果存在一个质数a，使a^(n-1) mod n != 1，则n一定不是质数，否则n可能是一个质数。

这看上去麻烦的算法其实好理解。它的原理便是使用费马小定理（Fermat's Little Theorem）的逆命题。该定理表述如下：

如果a是一个质数，且n是一个整数，那么(a^n)mod n = a mod n。

也就是说，如果a和n都是质数，当且仅当a^(n-1) mod n = 1时n是一个质数。米勒-拉宾算法便利用了这个定理进行验证。

下面是Java函数实现：

public static boolean isPrime(int n) {
    if (n < 2) return false;
    int r = 0;
    int d = n - 1;
    while ((d & 1) == 0) {
        r++;
        d >>= 1;
    }
    for (int a : new int[] {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
        if (n == a) {
            return true;
        }
        if (checkComposite(n, a, d, r)) {
            return false;
        }
    }
    return true;
}

在该函数中，