10兆までの素数を求める 其二

※この記事は以前のブログから移植したものです。

こんにちは、Sayahamittです。

素数探索プログラムがようやく進展しました。

受験生がこの時期に何をやっているんだと言われてしまいそうですが気にしません、

それ故の更新スパンの遅さ…です。

前回の寝ぼけクオリティコードでは検査対象の値(被検査値)をいちいち既知の全素数で割って調べていました。

この方法では、大きい素数(最大7桁程度)を検出する時に延々と割り算を繰り返さなければなりません。つまるところ、素数を素因数分解しようとしているようなもので演算の無駄が多いアルゴリズムでした。

解決方法として、被検査値を割る素数を2倍した値が被検査値より大きくなったら演算を切り上げる。など無駄な演算を極力しないようにしてみましたが効果的ではありませんでした。

そこで、良いアルゴリズムがないかとGoogle先生にお訊ねすると…

出てきた出てきた!!

「エラトステネスの篩」

他に同様の事をやっている方のサイトを見てみるとかなり高速なアルゴリズムなようです。

詳細はリンク先のwikipadiaに分かり易い説明が書いてあるのでここでは省きますが、ざっくり説明するとこうです。

1.探索する数のリストを用意(初項:2,公差:1,末項:nの等差数列)。

素数を格納するリストを用意。

2.探索リストのすべての値を探索リストの最初の数で割る。

割り切れた値は探索リストから除外。

3.探索リストを割った値を素数リストに格納して、探索リストから除外。

(1-3を素数リストの最大値の平方が探索リストの最大値より小さい間だけ繰り返す。)

4.最後に素数リストと探索リストに残った値が素数。

 

なんともシンプルなアルゴリズムでコレは速そうww

で、早速実装してみました。

#pragma comment(lib, "winmm.lib")
#include
#include
#include 
#include 
using namespace std;

//関数プロトタイプ
void output(int *lp_1,int *lp_p,int para,int time);//素数のテキストファイル出力関数
int eratos(int range);//エラトステネスの篩

void main(){
int Range=0;
int time_s,time_e;
bool chck_in=true;

cout<<"求める素数の上限を指定して下さい"<<endl; while(chck_in){ cin>>Range;//求める素数の最大値を入力。
  if(Range<2){cout<<"2以上の値を入力して下さい"<<endl;}else{chck_in=false;}
}
 time_s = timeGetTime();
 eratos(Range);//求める最大値を引数にエラトステネスの篩を呼び出す。
time_e = timeGetTime();
cout<<"実行時間:"<<time_e-time_s<<"ms"<<endl;
system("PAUSE");
}
//ここからエラトステネスの篩
int eratos(int range){
range=range-2;//0と1はリストに含めないので最大値から2を引く
int *list_1 = new int[range];//探索リスト用意
 int *list_p = new int[range];//素数リスト用意
 int cont=0;//探索リストを割る値
int ex_MAX=0;//探索リストの最大値
int time_Cs,time_Ce,time_Ct;

//探索数列配列初期化
for(int i=0;i<=range;i++){
list_1[i]=i+2;}
//素数数列配列初期化
for(int i=0;i<=range;i++){ list_p[i]=0;} cont=list_1[0];//最初に探索リストを割る値(=2)を代入 ex_MAX=list_1[range];当初の探索リストの最大値を代入 time_Cs = timeGetTime(); //探索数列を篩に掛ける for(int i=0;ex_MAX>=cont*cont;i++){//割る値の平方が探索リストの最大値より小さい間ループ
  for(int j=0;j<=range;j++){//探索リストを1つずつ割っていく
if(list_1[j]%(cont)==0){list_1[j]=0;}//割り切れた要素には0を代入
}
list_p[i]=cont;//素数リストに探索リストを割った数を代入
for(int k=0;k<=range;k++){if(list_1[k]!=0){cont=list_1[k];break;}}//次の探索リストを割る数を決定
  for(int k=0;k<=range;k++){if(list_1[k]!=0){ex_MAX=list_1[k];}}//探索リストの最大値を再設定
}
 time_Ce = timeGetTime();
//コンソールに素数を列挙することもできるが時間がかかるのでコメントアウトしてある。
//for(int j=0;j<=range;j++){if(list_p[j]!=0)cout<<list_p[j]<<endl;} 
//for(int j=0;j<=range;j++){if(list_1[j]!=0)cout<<list_1[j]<<endl;}
time_Ct = time_Ce-time_Cs;
cout<<"演算時間:"<<time_Ct<<"ms"<<endl;
output(list_1,list_p,range,time_Ct);
return 1 ;
delete [] list_1,list_p;
}

void output(int *lp_1,int *lp_p,int para,int time)
{
fstream file;

file.open("test_v0.2.txt", ios::out);
for(int j=0;j<=para;j++){if(lp_p[j]!=0)file<<lp_p[j]<<","<<flush;} 
for(int j=0;j<=para;j++){if(lp_1[j]!=0)file<<lp_1[j]<<","<<flush;}
file<<"演算時間:"<<time<<"ms"<<endl;
file.close();
}

ではでは、さらっと説明。

やってることは上で書いた通り被検査値をエラトステネスの篩に掛けているだけなのですが、

細かい処理について解説。

1.探索リストを配列で確保し2からnで初期化

素数リストも配列で確保しすべての要素を0で初期化

探索リストを割る値を変数contで確保

2.探索リストの最大値 en_MAXがcontの2乗以下の場合にループ実行

3.エラトステネスの篩実行

4.次のループでのcontとen_MAXを設定し2に戻る

5.結果を出力

エラトステネスの篩の処理の中で割り切れた探索リストの要素に0を代入しているのは、探索リストは2以上n以下の値しか存在しないので0を代入することで除外されたものとしているからです。

また、ループの最後に次の探索リストを割る数と探索リストの最大値を決定していますが、これはループ開始当初に探索リストの最大値として設定されていた要素の値が割りきれてしまった場合に他の被検査値よろしく0が代入されてしまうので設定しなおす必要があるからです。

これら2つの処理はwhile文で実装したほうがいいのかも知れませんが、配列を1つずつ辿る必要があるので要素指定変数の定義を命令中に含められるfor文をつかっています。細かいことはしらんっ☆(ゝω・)v

 

調べあげた素数をコンソールに出力してもいいのですが、ループ一回ごとにテキスト表示のシステムコールが割り込むので非常に時間が掛かりますww上限を100万とかに設定するなら止めとくのが賢明ですww

 

それで、結局前回と較べてどの程度速くなったのかというと…

core i3 2120 3.3Ghz, RAM DDR3-1333 16Gbyteの環境において

1299709まで(素数100万個)の演算時間(表示、ファイルへの出力を含まない)

前回:46913ms、今回:2096ms

おぉ!!これはwww

文字通り桁違いに速くなってますね!!

調子に乗ってもっと大きい数までの素数も演算してみました。

最大値 全体時間(ms) 演算時間(ms) 最大素数
10000000 218831 36134 9999991
100000000 2750870 969724 99999989

ファイルへの出力はやはり時間がかかるようですね;;

あと、結果として出力した素数の検証は行なっていないので悪しからず…

 

ではでは、また進展したら報告しますのんノシ

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です