今天讲点比较高级的算法，目的也很简单，求质数，但是应用一种新的算法 Miller-Rabin 算法，这是一种利用了概率和费马小定理的算法设计，有点玄乎吧，其实本人也是刚接触这种算法，这是一种纯数学的解法，如果各位不懂，当学习一下数学也好啊好，我们往下讲
首先了解基本的数学知识，费马小定理：
若 n 是素数，则对所有 1≤a≤n-1 的整数 a，有 a^(n-1) mod n=1;
作者 Fermat 很牛的数学家，在他在世的时候好像还没有计算机，不过今天我们要用这个定理来设计算法
分析这个定理可以知道，如果一个数是质数，那么它必定满足任意一个整数属于 (1，n-1) 范围有 a^(n-1) mod n=1，不懂？我们取逆否命题试试看，就是只要存在在 (1，n-1) 范围中的整数 a 使得 a^(n-1) mod n=1 不成立，那么这个数就不是素数，相信明白了吧，我们要确定一个数是否是素数，只要随机生成一系列的数 a，如果这些数 a 使 N 满足费马小定理的话那么就可以认定它是素数了，当然有个前提，就是这个推导只能在计算机领域内使用就跟我上次讲的用哥德巴赫猜想优化一道算法题目一样，在计算机可以运算的数的范围内可用，请不要在其他科学领域类使用
算法如下，原本是网络上的一个 C++ 算法，我改成 C
/*
* 费马小定理的应用，求质数
*Miller-Rabin 算法
*2008 12 27
*/
#include"stdio.h"
#include"stdlib.h"
#include"math.h"
#include"time.h"
int Btest(int a,int n)
{
int s = 0;
int t = n-1;
int i , j , k;
int x = 1;
int y;
i = 1;
do{
s++;
t = t / 2;
}while((t%2)!=1);
while(i < = t){
x = ( x * a ) % n;
i++;
}
if((x == 1) || ( x == n-1))
return 1;
for(j = 1 ; j <= s - 1 ; j++){
y = 1;
for(k = 1 ; k <= j ; k++)
{
y = 2 * y;
}
i = 1;
x = 1;
while(i <= ( y * t)){
x = ( x * a) % n;
i++;
}
if(x == n - 1)
return 1;
}
return 0;
}
int MillRab(int n)
{
int a;
/* 利用时间作为随机种子产生随机数 */
a=random((unsigned)time(0))%(n-3)+2;
return Btest(a,n);
}
int MillerRabin(int n,int k)
{
int i;
for(i=1;i<=k;i++)
{
if(MillRab(n)==0)return 0;
}
return 1;
}
int main (){/* 费马小定理的应用 */
int i;
int n=10000;/* 定义测试范围 */
int count=0;
printf ("2 3");/* 先输出 2 跟 3*/
for (i=5;i<=n;){/* 从 5 开始循环判断 */
if (MillerRabin (i , (int) log10 (i))){/* 符合条件？*/
printf("%d ",i);
count++;
}
i=i+2;
}
printf("nthere %d prime(s)n",count);
return 0;
}