取余算法

对一个大于1的自然数 n 依次判断 2 → √n 能否整除 n，如果发现一个数能整除 n，那么 n 不是素数，否则是。

C++代码如下：

bool isPrime(int n) 
{
    if (n <= 1)
        return false;i
    for (int i = 2; i * i < n; i++)
        if (n % i == 0)
            return false;
    return true;
}

这种方法时间复杂度很高，我们可以借助数论知识进行进一步的优化。

素数分布规律：当 n >= 5 时，如果 n 为素数，那么 n % 6 = 1 || n % 6 = 5，即 n 一定出现在 6x（x ≥ 1）两侧。换句话说，任意一个素数都可以被表示为 6x ± 1 , x ϵ N 的形式。

证明：

把 6x 附近的数用以下方式表示：
……(6x – 1), 6x, 6x+1, 2(3x+1), 3(2x+1), 2(3x +2), 6x + 5, 6(x+1)……
不在6x两侧的数为： 2(3x+1), 3(2x+1), 2(3x +2)，它们不是素数，所以素数出现在 6x 的两侧。

因此可以得到以下优化：

bool isPrime(int n) 
{
    if (n <= 1)
        return false;
    if (n <= 3)    
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i < n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

简单取余算法复杂度过高，故只适合于判定较小的数。