今天講點比較高級的算法，目的也很簡單，求質數，但是應用一種新的算法 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;
}