如何判断一个数是否是质数？

一个质数(Prime number)是只能被1和自身整除的正整数。要判断一个数n是否是质数,我们可以:

1. 找出n的所有因子(除了1和n之外的数),看其中的因子是否超过2个。如果超过2个,则n不是质数。
2. 由于质数的定义,我们只需要考虑从2到根号n之间的因子。因为如果n可以被a整除,那么n也可以被n/a整除。
3. 每找到一个因子,我们就可以提前返回false。只有在试到根号n都没有找到额外的因子,我们才能确定n是质数,返回true。
   例如,判断23是否是质数:

• 2不能整除23
• 3也不能整除23
• …
• 7不能整除23
• 到了根号23(约等于4.795)仍未找到额外因子,所以23是质数,返回true

这里是Java实现:

public boolean isPrime(int n) {
    if (n <= 1) return false; // 1不是质数
    if (n == 2) return true; // 2是唯一的偶质数 

    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;     // 找到因子,不是质数
        }
    }
    return true;    
}

这个方法先过滤掉1和2的特殊情况。然后从2开始遍历到根号n,每找到一个因子就直接返回false。如果试到根号n都未找到因子,则返回true。
例如isPrime(23)的过程是:

• i = 2, 23 % 2 != 0
• i = 3, 23 % 3 != 0
  …
• i = 7, 23 % 7 != 0
• 遍历结束,返回true, 23是质数
  所以这个方法利用了质数定义的性质,高效地判断一个数是否为质数,时间复杂度为O(根号n)。