そっすー!

こんばんは、ダンです。

今日は素数の日です!今決めました!

ってわけで素数を求める!
10億まで!

友達がインターンに行って、それで10億までの素数を求めるプログラムがどーとか言ってたから
僕も作ろうとね!

素数と言えば前回のEPOCHの時に1000万桁まで求めました。
その時使ったエラトステネスのふるいってアルゴリズム使って
今回は10億まで求めちゃおー★

10億までとかメモリが持たなさそうだから、メモリ節約をめっちゃ重視!

とりあえずchar型配列1bitに1桁対応させよう!
そして偶数除外しよう!
そしたら10億/8/2の1億バイト以内にできる!これならエラトさんに工夫しなくてもいける!

ってことでかきかき。

ものっすごいひっさびさにC言語使った!



#include<stdio.h>
#include<time.h>

#define SIZE 1000000000

char prime[SIZE/8/2+10];

void changeItoB(unsigned int num){
num = num/2-1;
int a = num%8; //aビット目
int b = num/8; //b個目
prime[b] |= 0x00000001 << a;
}

int judgePrime(unsigned int num){
num = num/2-1;
int a = num % 8; //aビット目
int b = num / 8; //b個目
if((prime[b] & (0x00000001 << a)) == (0x00000001 << a) )
return -1; //素数じゃない
else
return 0; //素数
}

void eratosan(void){
unsigned int p = 3,i;

// int count = 0,count2 = 1;//暇だから用
while(p <= SIZE){
for(i = p+p+p; i <= SIZE; i += p+p){
changeItoB(i);
}
i = p+2;
while(true){
if(judgePrime(i) == 0){
p = i;
break;
}
i+=2;
if(i >= SIZE){
return ;
}
}
/* if(count++ >= 10000000){
count=0;
printf("%d0000000個終わったよ!この時点での素数は%d!\n",count2++,p);
}*/
}
}

int main(void){
time_t start = time(NULL);
eratosan();

printf("2\n");
for(int i = 3; i <= SIZE;i+=2){
if(judgePrime(i) == 0){
printf("%d\n",i);
}
}
time_t t = time(NULL) - start;
printf("\n-----%dまでの素数を求めるのにかかった時間-----\n",SIZE);
printf("%ld秒\n",(long)t);
return 0;
}


ってわけでこんな感じになりました!

changeItoBは名前思いつかなかったんです。最初にノリでつけた名前そのまま。
IはintでBはbit!intからbitに変換してchangeする!って意味でつけました、まる。
動きは見て分かる通りそのまま!
prime[0]の0ビット目が数字3
prime[0]の1ビット目が数字5
     ・
     ・
     ・
prime[1]の0ビット目が数字19
     ・
     ・
     ・
     ・
と、対応させたので、そこをビット演算子のorを使ってビットを1に変えてます。
偶数とか2以下とか入れると挙動不審になるからやめてあげてね!

judgePrimeは、引数で受け取った数値があるビットに移動して素数か素数じゃないかを判断してくれる関数。
今回もビット演算で頑張った。
if((prime[b] & (0x00000001 << a)) == (0x00000001 << a) )
赤字の所を赤で囲んでるのは、&演算子と==演算子の優先度の関係。ここのカッコつけ忘れて30分悩んだ。

eratosanはそのままエラトステネスのふるい。
judgePrimeのところを変えたりすればもうちょっと高速化できる気がするけどもう疲れた。

そしてmain関数でえらとさん呼び出して素数を表示!

これで正常に動く・・・はず・・・。
改善するとこはいっぱいあるけど、ここまでできて満足しちゃった★
プログラマってそういう生き物だよね、うん。

ってわけで実行時間ー!

  ・
  ・
  ・
  ・
999999883
999999893
999999929
999999937

-----1000000000までの素数を求めるのにかかった時間-----
42秒


これはファイルに書きだした時の実行時間っ
このファイルを読み込む時も大変でした。
何個素数あるかわかりやすいように改行区切りにしたんですけど、僕の秀丸君1000万行までしか読み込んでくれないんです。
だからエディタを探して探してEmEditorと言うエディタにたどり着きました!
このEmEditorを使って開いた結果、10億までの素数の数は50847534個
本当にあってるか気になって10億までの素数の数でぐぐったけど、同じ数でした。
っということでとりあえず一安心。

ちなみに、ファイルとかディスプレイに書き出さなかったらもっと早いんですよこれ!
ってわけで表示部分をコメントアウトしてもう一回コンパイル、実行!
prime.png
はい、18秒!

っというわけで今日は素数のお話でしたーっ

コメント

非公開コメント

プロフィール

ダンギルバ

Author:ダンギルバ
ダンです!

~連絡先~
メール:

ついったーID:dangiruba

気軽にコメントとかください(*・ω・*)
大歓迎です(*・ω・*)

4のつく日は英語で更新!かも!!
暖かく見守ってください//
間違いあったらコメントくれると助かります><

ごゆっくりご覧ください。

カレンダー
プルダウン 降順 昇順 年別

04月 | 2024年05月 | 06月
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31 -


最新コメント
最新記事
月別アーカイブ
カテゴリ
FC2カウンター
ランキング
ブログランキング・にほんブログ村へ
にほんブログ村
にほんブログ村のランキング参加してます(´・ω・)ノ
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード