初学编程的人都会遇到一个经典的问题，写一个函数来判断一个数是否是素数。所有人都知道判断的原理：所谓素数，就是它除了能被1和它自己整除以外，不能被别的任何数整除。
我还记得我当年刚刚开始学习的时候，毫不犹豫的写下了这样的函数：
bool IsPrime1 (long num)
{
if(1 == num) return false;
for(long i = 2; i < num; ++i)
{
if(num % i == 0) //如果存在1和它本身以外的因数
return false;
}
return true;
}
应该说这个函数语法上没有错误，也能得到正确的结果，但是如果我们用这个函数去计算100万以内的素数个数，就会发现，它所用的时间是无法忍受的。分析一下就会发现，它判断一个数是否是素数，就要去计算从2开始每一个比它要小的数能否整除，如果计算的数很大，将会进行太多次循环。
如果我们仔细分析一个数，就会发现这个函数实际上进行了很多不必要的循环。判断一个数是否有1和它本身以外的因数，实际上并不需要从2遍历到num – 1。
我们来推导一下，假如有 a * b = num，可以肯定，a和b中必定有一个数小于等于num的平方根，一个数大于等于num的平方根，所以要找到一个数是否有因数，只要从2遍历到num的平方根就可以得出结果，然后我就讲函数做了相应的改进。
bool IsPrime2 (long num)
{
if(1 == num) return false;
int temp = sqrt(num);
for(long i = 2; i <= temp; ++i)
{
if(num % i == 0)
return false;
}
return true;
}
相比较于第一个函数，这个函数的效率提高了不少。它进行的循环的次数，只是第一个函数的次数的平方根。
那么还有没有更好的方法呢。显然是有的。
根据阴性素数定理和阴性合数定理以及阳性素数定理和阳性合数定理，我们知道除了2,3以外的素数，全都分布在6*N的左右（N为非零的自然数），换句话说，所有的素数都是6*N – 1 和 6*N + 1的形式。但是这样形式的数却并不全都是素数。
根据这个定理，我们可以进一步的优化判断素数的算法。
首先，如果一个数不是 6*N±1的形式，可以肯定这个数不是素数。
如果它是这样的形式，我们在进一步判断它是不是一个素数。对于一个6*N±1形式的数，首先可以确定它不可能被6*x（x <= N）形式的数整除。而对于6 *x ± 2形式的数，它就是 2*（3*x±1），所以如果6*N±1能被6 *x ± 2整除的话，那么显然6*N±1也应该能被2整除，但是显然6*N±1是一个奇数，不可能被2整除，由此可以断定它也不可能被6 *x ± 2形式的数整除。同样的道理，它也不应该能被6 *x ±4整除，对于6 *x ±3这样的数，它也可以表示为3*（2*x±1），也就是它是3的倍数，如果6*N±1能被它整除，也肯定能被3整除，这是矛盾的，所以可以确定6*N±1也不能被6*x±3整除。所以在对于6*N±1形式的数进行循环寻找因数的时候，可以跳过诸如6*x，6 *x ± 2，6 *x ± 3，6 *x ± 4。换句话说，假如6 *N ± 1的因数存在，它必然是6 *x ± 1的形式。这样我们就可以进一步的减少循环的次数。如果寻找因数的时候，我们从i = 5开始循环，它是6*1-1的形式，我们只需要判断i和i+2（即6*1+1的形式）是不是他的因数，然后进行下一步循环的时候，我们不需要让i++，而找到下一个6*2-1，显然就是让i+=6即可，中间的数字不需要再进行判断可以直接跳过，这样大大的减少循环判断的次数来提高效率。代码如下：
bool IsPrime3(long num)
{
if(2 == num || 3 == num) returntrue; //对于2,3单独处理
if(num % 6 != 1 && num % 6 != 5) //直接排除非6*N±1形式的数
return false;
else
{
int temp = sqrt(num);
for(long i = 5; i <= temp; i += 6)//对6*N±1形式的数进行判断
{
if(num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
}
我们可以通过一些代码简单的测试一下第二个和第三个函数执行需要的时间。为了显示区别，我们分别让他们判断50万个数是不是素数：
int main()
{
clock_t t1, t2;
t1 = clock();
for(long i = 2; i < 500000; ++i)
IsPrime2(i);
t2 = clock();
cout << "IsPrime2函数所用CPU时间 ms ：" << t2 - t1 <<endl;
t1 = clock();
for(long i = 2; i < 500000; ++i)
IsPrime3(i);
t2 = clock();
cout << "IsPrime3函数所用CPU时间 ms ：" << t2 - t1 <<endl;
return 0;
}
注：运行程序需要头文件如下：
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
执行结果如下：
我还记得我当年刚刚开始学习的时候，毫不犹豫的写下了这样的函数：
bool IsPrime1 (long num)
{
if(1 == num) return false;
for(long i = 2; i < num; ++i)
{
if(num % i == 0) //如果存在1和它本身以外的因数
return false;
}
return true;
}
应该说这个函数语法上没有错误，也能得到正确的结果，但是如果我们用这个函数去计算100万以内的素数个数，就会发现，它所用的时间是无法忍受的。分析一下就会发现，它判断一个数是否是素数，就要去计算从2开始每一个比它要小的数能否整除，如果计算的数很大，将会进行太多次循环。
如果我们仔细分析一个数，就会发现这个函数实际上进行了很多不必要的循环。判断一个数是否有1和它本身以外的因数，实际上并不需要从2遍历到num – 1。
我们来推导一下，假如有 a * b = num，可以肯定，a和b中必定有一个数小于等于num的平方根，一个数大于等于num的平方根，所以要找到一个数是否有因数，只要从2遍历到num的平方根就可以得出结果，然后我就讲函数做了相应的改进。
bool IsPrime2 (long num)
{
if(1 == num) return false;
int temp = sqrt(num);
for(long i = 2; i <= temp; ++i)
{
if(num % i == 0)
return false;
}
return true;
}
相比较于第一个函数，这个函数的效率提高了不少。它进行的循环的次数，只是第一个函数的次数的平方根。
那么还有没有更好的方法呢。显然是有的。
根据阴性素数定理和阴性合数定理以及阳性素数定理和阳性合数定理，我们知道除了2,3以外的素数，全都分布在6*N的左右（N为非零的自然数），换句话说，所有的素数都是6*N – 1 和 6*N + 1的形式。但是这样形式的数却并不全都是素数。
根据这个定理，我们可以进一步的优化判断素数的算法。
首先，如果一个数不是 6*N±1的形式，可以肯定这个数不是素数。
如果它是这样的形式，我们在进一步判断它是不是一个素数。对于一个6*N±1形式的数，首先可以确定它不可能被6*x（x <= N）形式的数整除。而对于6 *x ± 2形式的数，它就是 2*（3*x±1），所以如果6*N±1能被6 *x ± 2整除的话，那么显然6*N±1也应该能被2整除，但是显然6*N±1是一个奇数，不可能被2整除，由此可以断定它也不可能被6 *x ± 2形式的数整除。同样的道理，它也不应该能被6 *x ±4整除，对于6 *x ±3这样的数，它也可以表示为3*（2*x±1），也就是它是3的倍数，如果6*N±1能被它整除，也肯定能被3整除，这是矛盾的，所以可以确定6*N±1也不能被6*x±3整除。所以在对于6*N±1形式的数进行循环寻找因数的时候，可以跳过诸如6*x，6 *x ± 2，6 *x ± 3，6 *x ± 4。换句话说，假如6 *N ± 1的因数存在，它必然是6 *x ± 1的形式。这样我们就可以进一步的减少循环的次数。如果寻找因数的时候，我们从i = 5开始循环，它是6*1-1的形式，我们只需要判断i和i+2（即6*1+1的形式）是不是他的因数，然后进行下一步循环的时候，我们不需要让i++，而找到下一个6*2-1，显然就是让i+=6即可，中间的数字不需要再进行判断可以直接跳过，这样大大的减少循环判断的次数来提高效率。代码如下：
bool IsPrime3(long num)
{
if(2 == num || 3 == num) returntrue; //对于2,3单独处理
if(num % 6 != 1 && num % 6 != 5) //直接排除非6*N±1形式的数
return false;
else
{
int temp = sqrt(num);
for(long i = 5; i <= temp; i += 6)//对6*N±1形式的数进行判断
{
if(num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
}
我们可以通过一些代码简单的测试一下第二个和第三个函数执行需要的时间。为了显示区别，我们分别让他们判断50万个数是不是素数：
int main()
{
clock_t t1, t2;
t1 = clock();
for(long i = 2; i < 500000; ++i)
IsPrime2(i);
t2 = clock();
cout << "IsPrime2函数所用CPU时间 ms ：" << t2 - t1 <<endl;
t1 = clock();
for(long i = 2; i < 500000; ++i)
IsPrime3(i);
t2 = clock();
cout << "IsPrime3函数所用CPU时间 ms ：" << t2 - t1 <<endl;
return 0;
}
注：运行程序需要头文件如下：
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
执行结果如下：
