[数学] 判素数

质数（prime number）又称素数，有无限个。除了1和它本身以外不再有其他的除数整除。根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积，最小的质数是2。

所谓素数是指除了1和它本身以外，不能被任何整数整除的数。

例如17就是素数，因为它不能被2~16的任一整数整除。因此判断一个整数m是否是素数，只需把m被2~m-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数。

另外判断方法还可以简化。m不必被2~m-1之间的每一个整数去除，只需被2~sqrt(m)之间的每一个整数去除就可以了。如果m不能被2~sqrt(m)间任一整数整除，m必定是素数。例如判别17是是否为素数，只需使17被2~4之间的每一个整数去除，由于都不能整除，可以判定17是素数。（原因：因为如果m能被2~m-1之间任一整数整除，其二个因子必定有一个小于或等于sqrt(m)，另一个大于或等于sqrt(m)。例如16能被2,4,8整除，16=28,2小于4,8大于4，16=44,4=√16，因此只需判定在2~4之间有无因子即可）

#include <stdio.h>

bool bIsPrime(int N)
{
    if(N < 2) return false;

    for (int i = 2; i*i <= N; i++)
        if(N % i == 0)
            return false;

    return true;
}

int main()
{
    for (int i = 0; i < 20; i++)
    {
        if(bIsPrime(i))
        {
            printf("%d is prime\n", i);
        }
        else
        {
            printf("%d is not prime\n", i);
        }
    }
    return 0;
}

质数的个数是无穷的。

欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：

假设质数只有有限的 n 个，从小到大依次排列为 p1，p2，……，pn，设 N=p1×p2×……×pn，那么，N+1 是素数或者不是素数。

    如果 N+1 为合数，因为任何一个合数都可以分解为几个素数的积；而 N 和 N+1 的最大公约数是 1，所以 N+1 不可能被 p1，p2，……，pn 整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。

因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。