所谓质数，指的是除了 1 和它本身外不能被其他自然数整除的自然数，与此相对应的是合数，合数指的是除了1 和它本身外还能被其他自然数整除的自然数。最小的质数是 2，合数能够分解为两个数的乘积，其中一个数比该合数的平方根小，另一个数比该合数的平方根大，这是合数的一个最为重要的性质。

由以上关于质数、合数的定义以及性质，可以得出判断一个数是否为质数至少有以下三种方法：

最笨的方法

1
2
3
4
5
6
7
8
9
10
11
public static boolean isPrime(int N)
{
    if (N < 2)
        return false;
    for (int i = 2; i < N; i++)
    {
        if (N % i == 0)
            return false;
    }
    return true;
}

一个数不可能被比它的一半还要大的数整除的

上面的方法是一个非常笨的方法，没有必要死板地按照定义，非得把一个数从除了它自身和 1 之外的所有数一个个地除完，因为一个数是不可能被比它的一半还要大的数整除的，例如 100 是断然不能被诸如 51、52、53... 这些比 50 还要大的数整除的，所以优化以上代码后，有了方法二

1
2
3
4
5
6
7
8
9
10
11
public static boolean isPrime(int N)
{
    if (N < 2)
        return false;
    for (int i = 2; i <= N/2; i++)
    {
        if (N % i == 0)
            return false;
    }
    return true;
}

任何合数都能够分解为一个比它的平方根小的数和一个比它的平方根大的数的乘积

除了以上两种方法之外，实际上还有一种更为优化的方法，利用任何合数都能够分解为一个比它的平方根小的数和一个比它的平方根大的数的乘积

1
2
3
4
5
6
7
8
9
10
11
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;
}