C++面试宝典第5题：判断素数

题目

????????判断一个正整数是否为素数有哪几种方法，每种方法的时间复杂度怎么样。

解析

????????素数又称质数，是指在大于1的自然数中，除了1和它本身以外，不再有其他因数的自然数。素数只有1和它本身两个正因数，最小的素数是2，素数的个数是无穷的。

????????埃拉托斯特尼筛法（Sieve of Eratosthenes），简称“筛法”，是一种简单判定素数的算法，也是一种历史悠久的筛法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。其方法是，给出要筛数值的范围n，先用2去筛，把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；不断重复下去。

????????根据上面的思路，我们给出了下面的示例代码。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool IsPrime3(unsigned int uiNum)
{
    if (uiNum <= 1)
    {
        return false;
    }

    vector<bool> vctPrime(uiNum + 1, true);
    vctPrime[0] = false;
    vctPrime[1] = false;
    unsigned int uiTemp = (unsigned int)sqrt(uiNum);
    for (unsigned int i = 2; i <= uiTemp; i++)
    {
        if (vctPrime[i])
        {
            for (unsigned int j = i * i; j <= uiNum; j += i)
            {
                vctPrime[j] = false;
                if (j == uiNum)
                {
                    break;
                }
            }
        }
    }

    return vctPrime[uiNum];
}

int main()
{
    for (unsigned int i = 0; i < 100; i++)
    {
        if (IsPrime3(i))
        {
            cout << i << " ";
        }
    }

    return 0;
}

????????通过上面的代码可以得知，埃拉托斯特尼筛法的时间复杂度为O(nlogn)。

????????判断一个数是否为素数，最直接也最常用的方法为：循环遍历从2到该数的平方根之间的所有整数，尝试能否整除该数。如果存在能整除该数的整数，则该数不是素数；否则，该数是素数。这种方法的时间复杂度为O(sqrt(n))，具体实现，可参考下面的示例代码。

#include <iostream>
#include <cmath>
#include <Windows.h>
using namespace std;

bool IsPrime1(unsigned int uiNum)
{
    if (uiNum <= 1)
    {
        return false;
    }

    unsigned int uiTemp = (unsigned int)sqrt(uiNum);
    for (unsigned int i = 2; i <= uiTemp; i++)
    {
        if (uiNum % i == 0)
        {
            return false;
        }
    }

    return true;
}

int main()
{
    unsigned int uiTick = GetTickCount();
    for (unsigned int i = 0; i < 10000000; i++)
    {
        IsPrime1(i);
    }

    // 输出：2719ms
    cout << GetTickCount() - uiTick << "ms" << endl;
    return 0;
}

????????还有一种更高效的方法，需要用到素数分布的规律。该规律为：大于等于5的素数，一定和6的倍数相邻。比如：素数5、7在6的两侧，素数11、13在12的两侧，素数17、19在18的两侧。

????????该分布规律的证明其实并不难，假设有一个数x>=1，则可将大于等于5的自然数N表示为：6x-1、6x、6x+1、6x+2、6x+3、6x+4、6x+5、6(x+1）、6(x+1)+1、...。可以看到，不在6的倍数两侧的数为：6x+2、6x+3、6x+4。由于6x+2为2(3x+1)，6x+3为3(2x+1)，6x+4为2(3x+2)，故它们一定不是素数。再除去6x本身，则素数只可能出现在6x的相邻两侧。但是注意，在6x的相邻两侧，并不一定就是素数。

????????对于N为6x-1、6x+1这两种情况，可以将其表示为：6i-1、6i、6i+1、6i+2、6i+3、6i+4。如果N能被6i、6i+2、6i+4整除，则N至少得是一个偶数，但6x-1、6x+1明显为一个奇数，故不成立。如果N能被6i+3整除，则N至少能被3整除，但6x-1、6x+1不可能被3整除，故亦不成立。综上，只需要考虑6i-1和6i+1的情况，即：循环的步长可以设置为6，每次判断循环变量k和k+2的情况。理论上，该方法的时间复杂度为O(sqrt(n)/3)。

????????根据上面的思路，我们给出了下面的示例代码。

#include <iostream>
#include <cmath>
#include <Windows.h>
using namespace std;

bool IsPrime2(unsigned int uiNum)
{
    // 单独处理0和1
    if (uiNum <= 1)
    {
        return false;
    }

    // 单独处理2和3
    if (uiNum == 2 || uiNum == 3)
    {
        return true;
    }

    // 不在6的倍数两侧的，一定不是素数
    if (uiNum % 6 != 1 && uiNum % 6 != 5)
    {
        return false;
    }

    // 在6的倍数两侧的，也可能不是素数
    unsigned int uiTemp = (unsigned int)sqrt(uiNum);
    for (unsigned int i = 5; i <= uiTemp; i += 6)
    {
        // 只需要考虑6i-1和6i+1的情况
        if (uiNum % i == 0 || uiNum % (i + 2) == 0)
        {
            return false;
        }
    }
        
    // 排除所有情况，剩余的肯定是素数
    return 1 ;
}

int main()
{
    unsigned int uiTick = GetTickCount();
    for (unsigned int i = 0; i < 10000000; i++)
    {
        IsPrime2(i);
    }

    // 输出：1015ms
    cout << GetTickCount() - uiTick << "ms" << endl;
    return 0;
}

总结

????????通过这道题，我们学习了判断一个正整数是否为素数的若干方法。既有历史悠久的埃拉托斯特尼筛法，也有常用的遍历法。在遍历法的基础上，我们利用素数的分布规律，对算法进行了优化，提升了其运行效率，降低了其时间复杂度。