还是太糟了，我们现在要做的对于大型素数的判断，那个素数表倒顶个P用！当然，我们可以利用动态的素数表来进行优化，这就是大学生的做法了。但是动态生成素数表的策略又复杂又没有效率，所以我们还是直接跳跃到专家的做法吧：
根据上面讲到的费马小定理，对于两个互质的素数N和P,必有：N^（P-1）%P=1 ,那么我们通过这个性质来判断素数吧，当然，你会担心当P很大的时候乘方会很麻烦。不用担心！我们上面不是有个快速的幂模算法么？好好的利用蒙格马利这位大数学家为我们带来的快乐吧！
算法思路是这样的：
对于N,从素数表中取出任意的素数对其进行费马测试，如果取了很多个素数，N仍未测试失败，那么则认为N是素数。当然，测试次数越多越准确，但一般来讲50次就足够了。另外，预先用"小学生"的算法构造一个包括500个素数的数组，先对Q进行整除测试，将会大大提高通过率，方法如下：
6）下面是专家的做法：
[cpp]
bool IsPrime3（unsigned n）
{
if （ n < 2 ）
{
// 小于2的数即不是合数也不是素数
throw 0;
}
static unsigned aPrimeList[] = {
2, 3, 5, 7, 11, 17, 19, 23, 29, 31, 41,
43, 47, 53, 59, 67, 71, 73, 79, 83, 89, 97
};
const int nListNum = sizeof（aPrimeList） / sizeof（unsigned）；
for （int i=0;i<nListNum;++i）
{
// 按照素数表中的数对当前素数进行判断
if （1!=Montgomery（aPrimeList[i],n-1,n）） // 蒙格马利算法
{
return false;
}
}
return true;
}
bool IsPrime3（unsigned n）
{
if （ n < 2 ）
{
// 小于2的数即不是合数也不是素数
throw 0;
}
static unsigned aPrimeList[] = {
2, 3, 5, 7, 11, 17, 19, 23, 29, 31, 41,
43, 47, 53, 59, 67, 71, 73, 79, 83, 89, 97
};
const int nListNum = sizeof（aPrimeList） / sizeof（unsigned）；
for （int i=0;i<nListNum;++i）
{
// 按照素数表中的数对当前素数进行判断
if （1!=Montgomery（aPrimeList[i],n-1,n）） // 蒙格马利算法
{
return false;
}
}
return true;
} OK,这就专家的作法了。
等等，什么？好像有点怪，看一下这个数29341,它等于13 * 37 * 61,显然是一个合数，但是竟通过了测试！！哦，抱歉，我忘了在素数表中加入13,37,61这三个数，我其实是故意的，我只是想说明并费马测试并不完全可靠。
现在我们发现了重要的一点，费马定理是素数的必要条件而非充分条件。这种不是素数，但又能通过费马测试的数字还有不少，数学上把它们称为卡尔麦克数，现在数学家们已经找到所有10 ^ 16以内的卡尔麦克数，最大的一个是9585921133193329.我们必须寻找更为有效的测试方法。数学家们通过对费马小定理的研究，并加以扩展，总结出了多种快速有效的素数测试方法，目前最快的算法是拉宾米勒测试算法，下面介绍拉宾米勒测试。
================================================================
7.拉宾米勒测试
拉宾米勒测试是一个不确定的算法，只能从概率意义上判定一个数可能是素数，但并不能确保。算法流程如下：
1.选择T个随机数A,并且有A<N成立。
2.找到R和M,使得N=2*R*M+1成立。
快速得到R和M的方式：N用二进制数B来表示，令C=B-1.因为N为奇数（素数都是奇数），所以C的最低位为0,从C的最低位的0开始向高位统计，一直到遇到第一个1.这时0的个数即为R,M为B右移R位的值。
3.如果A^M%N=1,则通过A对于N的测试，然后进行下一个A的测试
4.如果A^M%N!=1,那么令i由0迭代至R,进行下面的测试
5.如果A^（（2^i）*M）%N=N-1则通过A对于N的测试，否则进行下一个i的测试
6.如果i=r,且尚未通过测试，则此A对于N的测试失败，说明N为合数。
7.进行下一个A对N的测试，直到测试完指定个数的A
通过验证得知，当T为素数，并且A是平均分布的随机数，那么测试有效率为1 / （ 4 ^ T ）。如果T > 8那么测试失误的机率就会小于10^（-5），这对于一般的应用是足够了。如果需要求的素数极大，或着要求更高的保障度，可以适当调高T的值。
下面是代码：
[cpp]
bool RabbinMillerTest（ unsigned n ）
{
if （n<2）
{
// 小于2的数即不是合数也不是素数
throw 0;
}
const unsigned nPrimeListSize=sizeof（g_aPrimeList）/sizeof（unsigned）；//求素数表元素个数
for（int i=0;i<nPrimeListSize;++i）
{
// 按照素数表中的数对当前素数进行判断
if （n/2+1<=g_aPrimeList[i]）
{
// 如果已经小于当前素数表的数，则一定是素数
return true;
}
if （0==n%g_aPrimeList[i]）
{
// 余数为0则说明一定不是素数
return false;
}
}
// 找到r和m,使得n = 2^r * m + 1;
int r = 0, m = n - 1; // （ n - 1 ） 一定是合数
while （ 0 == （ m & 1 ） ）
{
m 》= 1; // 右移一位
r++; // 统计右移的次数
}
const unsigned nTestCnt = 8; // 表示进行测试的次数
for （ unsigned i = 0; i < nTestCnt; ++i ）
{
// 利用随机数进行测试，
int a = g_aPrimeList[ rand（） % nPrimeListSize ];
if （ 1 != Montgomery（ a, m, n ） ）
{
int j = 0;
int e = 1;
for （ ; j < r; ++j ）
{
if （ n - 1 == Montgomery（ a, m * e, n ） ）
{
break;
}
e 《= 1;
}
if （j == r）
{
return false;
}
}
}
return true;
}
bool RabbinMillerTest（ unsigned n ）
{
if （n<2）
{
// 小于2的数即不是合数也不是素数
throw 0;
}
const unsigned nPrimeListSize=sizeof（g_aPrimeList）/sizeof（unsigned）；//求素数表元素个数
for（int i=0;i<nPrimeListSize;++i）
{
// 按照素数表中的数对当前素数进行判断
if （n/2+1<=g_aPrimeList[i]）
{
// 如果已经小于当前素数表的数，则一定是素数
return true;
}
if （0==n%g_aPrimeList[i]）
{
// 余数为0则说明一定不是素数
return false;
}
}
// 找到r和m,使得n = 2^r * m + 1;
int r = 0, m = n - 1; // （ n - 1 ） 一定是合数
while （ 0 == （ m & 1 ） ）
{
m 》= 1; // 右移一位
r++; // 统计右移的次数
}
const unsigned nTestCnt = 8; // 表示进行测试的次数
for （ unsigned i = 0; i < nTestCnt; ++i ）
{
// 利用随机数进行测试，
int a = g_aPrimeList[ rand（） % nPrimeListSize ];
if （ 1 != Montgomery（ a, m, n ） ）
{
int j = 0;
int e = 1;
for （ ; j < r; ++j ）
{
if （ n - 1 == Montgomery（ a, m * e, n ） ）
{
break;
}
e 《= 1;
}
if （j == r）
{
return false;
}
}
}
return true;
}