今日は少し高度なアルゴリズムについて話します。目的は非常にシンプルで、素数を求めることですが、新しいアルゴリズムであるミラーラビンのアルゴリズムを使用します。これは確率とフェルマーの小定理を利用したアルゴリズム設計で、少し神秘的ですが、私自身もこのアルゴリズムについて初めて触れるので、これは純粋な数学的な解法です。理解できない場合は、数学を学ぶこともできます。それでは続けましょう。
まず、基本的な数学の知識であるフェルマーの小定理を理解しましょう：
素数 n の場合、1≤a≤n-1 のすべての整数 a に対して、a^(n-1) mod n=1 が成り立ちます。
フェルマーは非常に優れた数学者であり、彼が生きていた時代にはまだコンピュータは存在していなかったようですが、今日はこの定理を使用してアルゴリズムを設計する必要があります。
この定理を分析すると、ある数が素数である場合、任意の整数 a が (1、n-1) の範囲に存在し、a^(n-1) mod n=1 が成り立つことがわかります。理解できない場合は、逆の命題を試してみましょう。つまり、(1、n-1) の範囲に存在する整数 a が存在し、a^(n-1) mod n=1 が成り立たない場合、その数は素数ではないということです。理解できたと思いますが、数が素数であるかどうかを確認するには、ランダムにいくつかの数 a を生成し、これらの数 a がフェルマーの小定理を満たす場合、それを素数と見なすことができます。もちろん、前提条件があります。この推論はコンピュータの領域でのみ使用できます。先ほど話したゴールドバッハの予想を最適化するためのアルゴリズム問題と同じです。計算機で計算可能な数の範囲内でのみ使用してください。他の科学領域では使用しないでください。
以下はアルゴリズムです。もともとはネット上の C++ アルゴリズムでしたが、C に変更しました。
/*
* フェルマーの小定理の応用、素数の求め方
* ミラーラビンのアルゴリズム
* 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;
}