教你如何编写一个Java函数来判断一个数是不是质数

判断一个数是否为质数是编程中常见的一个问题。质数是指除了1和它本身以外，不能被其他整数整除的数。本文将教授如何编写一个Java函数来判断一个数是否为质数。

质数判断算法

判断一个数是否为质数，在算法上并不复杂。可以采用最简单的方法，即遍历所有小于该数的自然数，判断该数是否被其整除。如果存在一个除了1和该数本身的因子，则该数不是质数。反之，如果不存在这样的因子，那么该数是质数。如判断数字n是否为质数：

public boolean isPrime(int n) {

    if (n <= 1) { // 判断该数是否小于等于1

        return false;

    }

    for (int i = 2; i < n; i++) { // 循环遍历能否被整除

        if (n % i == 0) { // 如果存在一个因子,则不是质数

            return false;

        }

    }

    return true; // 否则就是质数

}

上述算法对所有小于该数的整数进行了遍历，时间复杂度为O(n)，显然效率较低。但是，我们可以进行一定的优化。

优化算法

通过观察质数的定义，我们发现判断一个数是否为质数，其实并不需要遍历所有小于该数的自然数。比如判断一个数n是否为质数，只需要遍历2到sqrt(n)就可以，因为如果n不是质数，那么一定存在一个因子小于或等于sqrt(n)。如：

public boolean isPrime(int n) {

    if (n <= 1) {

        return false;

    }

    int sqrt = (int) Math.sqrt(n); // 对n开平方

    for (int i = 2; i <= sqrt; i++) { // 遍历2到sqrt(n)

        if (n % i == 0) {

            return false;

        }

    }

    return true;

}

这种算法在时间复杂度上是O(sqrt(n))，效率得到了显著提高。

编写测试用例

为了验证我们的isPrime函数是否能正确判断一个数是否为质数，我们需要编写一些测试用例。测试用例需包含质数和非质数两种情况。

@Test

public void testIsPrime() {

    // 测试非质数

    assertFalse(isPrime(0));

    assertFalse(isPrime(1));

    assertFalse(isPrime(4));

    assertFalse(isPrime(6));

    assertFalse(isPrime(8));

    assertFalse(isPrime(9));

    assertFalse(isPrime(10));

    assertFalse(isPrime(12));

    // 测试质数

    assertTrue(isPrime(2));

    assertTrue(isPrime(3));

    assertTrue(isPrime(5));

    assertTrue(isPrime(7));

    assertTrue(isPrime(11));

    assertTrue(isPrime(13));

    assertTrue(isPrime(17));

    assertTrue(isPrime(19));

}

单元测试很重要，不但能够验证函数是否符合预期设计，还可以让我们在修改函数时快速检测是否会对其他代码造成不良影响。

总结

判断一个数是否为质数，在算法上并不复杂。通过遍历每一个小于该数的自然数，判断该数是否被整除即可。为了优化时间复杂度，我们可以仅遍历2到sqrt(n)之间的自然数。在编写Java函数时，我们应编写相应的测试用例来验证函数是否按照预期工作。