Java函数实现：如何判断一个数是否为质数？

判断一个数是否为质数是一个经典的问题，在计算机科学中也有很多种方法可以实现。本文将介绍几种常见的Java函数实现方法来解决这个问题。

1. 暴力枚举法

暴力枚举法是最直接的方法，该方法的基本思想是，从2到n-1逐个遍历n的因子，如果n能被任意一个数整除，则判定n为非质数，否则n为质数。

Java代码实现：

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

这种方法最简单，但也最慢，时间复杂度为O(n)，当n很大时计算时间过长。

2. 去掉偶数法

根据素数的定义，大于2的偶数都不是质数，因此可以先判断n是否是偶数，如果是，则直接返回false。如果n是奇数，则只需要从3到sqrt(n) （或sqrt(n)+1）逐个检查奇数是否可以整除n。

Java代码实现：

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

这种方法的时间复杂度为O(sqrt(n))，稍微快一些。

3. 筛法

筛法是另外一种高效的方法，通过筛子来一次性地计算所有小于等于n的质数。首先需要一个boolean数组来表示哪些数字是质数。从2开始遍历数组，如果当前数字是质数，然后将它的倍数标记为非质数。具体来说，我们可以从2开始，依次标记2的倍数（4,6,8,..）为非质数，然后再标记3的倍数（6,9,12,...），一直到sqrt(n)。

Java代码实现：

public static boolean[] sieve(int n) {
    boolean[] primes = new boolean[n+1];
    Arrays.fill(primes, true);
    primes[0] = primes[1] = false;
    int sqrt = (int)Math.sqrt(n);
    for (int i = 2; i <= sqrt; i++) {
        if (primes[i]) {
            for (int j = i*i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }
    return primes;
}

public static boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    boolean[] primes = sieve(n);
    return primes[n];
}

这种方法的时间复杂度为O(nloglogn)，但空间复杂度比较大，为O(n)。

4. 费马小定理

费马小定理是一个基于数论的方法。它告诉我们，如果p是质数，则a^(p-1) ≡ 1 (mod p)，其中a是任意整数，mod运算表示取余数。如果n不是质数，则a^(n-1) != 1(mod n)。在判断一个数是否是质数时，随机选取a，计算a^(n-1) % n，如果结果不为1，则n必定不是质数。

Java代码实现：

public static boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    Random rand = new Random();
    for (int i = 0; i < 5; i++) {
        int a = rand.nextInt(n-1) + 1;
        if (modPow(a, n-1, n) != 1) {
            return false;
        }
    }
    return true;
}

public static int modPow(int a, int b, int m) {
    if (b == 0) {
        return 1;
    }
    long t = modPow(a, b/2, m);
    long res = t * t % m;
    if (b % 2 == 1) {
        res = res * a % m;
    }
    return (int)res;
}

这种方法虽然速度比较快，但也有漏判的情况，需要进行多次随机测试才能确定结果正确性。

总结

在实际应用中，选用哪种方法要视具体情况而定。如果需要快速判断多个数字是否是质数，可以使用筛法或费马小定理；如果只需要判断一个数字是否是质数，可以使用去掉偶数法。