rokiの戯言

コミュ障のコンピュータオタクがなんかほざきます。

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

この記事は新ブログ「mittBlog」に移植しました。

移植先の方がソースコードが見やすくなっています。

 

こんにちは、rokiです。 

ITproの記事を漁っていたら『10兆までの素数のリストを作ってみませんか?』なんてそそるエントリを見つけちゃいました。

なんでも、10兆まで素数を求めるとなると巨大な変数の扱いや大きなテキストファイルの出力、演算の並列化などが必要になるのでプログラマとしての基本的な技能が試されるとのこと。 

時間も無いし見習いC++erだけど、 地味にやってけば技術が身につくのではないかという儚い希望のもとに挑戦してみることにしました。

 

それで、寝ぼけ眼で15分くらいで書いたコードがコレ 

取り敢えず素数を100万個求めるようにしてみました。 

  • #pragma comment(lib, "winmm.lib")

    #include<fstream>
    #include<iostream>
    #include <windows.h>
    #include <mmsystem.h> 
    using namespace std;

    //関数プロトタイプ
    bool judg_prime(int jed_num,const int *ppa,int para); //素数判定関数
    void output(int *wpa,int para,int time); //ファイル出力関数

    void main(){
    const int MAX=100000;
     int a,i; 
     int *pa = new int [MAX]; //素数配列をヒープに確保
     int time_to,time_s,time_e;

     cin>>a; //適当な値を入力してEnterを押すと演算開始
     time_s = timeGetTime();  //演算開始時の時間を取得
     a=2; //ここでaに2を代入するので上で何を入力しても関係なし
     pa[0]=a; //素数配列の要素0に2を代入
     cout<<pa[0]<<endl;//最初の素数、2を表示

     for(i=1;i<=MAX-1 && a<=2147483646;i++){//素数配列が一杯になるかaがint型の最大値を超えるとループ脱出
    a++;
     if(judg_prime(a,pa,i-1)==true){  //aが素数なら素数配列に追加
    pa[i]=a;
    cout<<pa[i]<<endl;}
     else{i--;}  //aが素数でない場合はカウントパラメータをデクリメントする
    }
     time_e = timeGetTime(); //演算終了時の時間を取得
     time_to = time_e-time_s; //演算に掛かった時間を算出
     output(pa,i,time_t); //素数配列、演算に掛かった時間をファイルに出力
     delete [] pa; //素数配列のメモリを解放

     cout<<"演算時間:"<<time_to<<"ms"<<endl;
    }

    bool judg_prime(int jed_num,const int *ppa,int para){
    //(素数か判定する値,素数配列へのポインタ,配列の要素数(既に求まっている素数の数))
    int flag=1;

    for(int n=0;n<=para;n++){
    if(jed_num%ppa[n]==0){flag=0; break;}
    }//与えられた値が既知の素数(素数配列の全要素)でそれぞれ割れるかチェック

    if(flag==1){
    return true;
    }else{
    return false;}
    }

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

    file.open("test.txt", ios::out);
    for(int i=1;i<=para;i++){
    file<< wpa[i-1] << endl;
    }
    file<<"演算時間:"<<time<<"ms"<<endl;
    file.close();
    }

一応大雑把に説明、

1. int型の変数 a 、int型の配列 pa を宣言

2. a の初期値を 2 として配列 pa に格納する

3. a の値を1つ増やして pa に格納されてる素数全てで割ってみる(素数判定関数) 

4. a がいずれの素数でも割り切れなかったらその値を pa に格納、割り切れたら何もしない

5. 4に戻る(ループ)

 

で、何となくボヤッと書いて実行してみて気づいたんですけど。

 

このアルゴリズム遅すぎwww

 

なんかもう遅すぎて話にならないwwカタツムリよりおせぇよw

100万個の素数を求めるのに 49.146秒、1億個では1日経っても終わってなかったww

なんで遅いって、値を1つ評価するのに素数配列の既知の素数が入ってる要素を全部参照して一つ一つで被評価値を割ってるからなんだけど。

 

高速化するには 

・2や3の倍数は評価対象から外す 

・ 評価時に既知の素数を全探索するのを止める

すぐに思いつくアルゴリズムの改善点はこのくらいorz

きっともっと効率的に素数を求める方法があるはず...そのうち調べよう;;;

 

単に素数を求めるアルゴリズム以外にも、演算の並列化とか範囲の限定とか改善点は山積なんですけどね。15分クオリティならこんなもんでしょ。

 

ではでは、進んだらまた報告しまーす。ノシ~