そっすー！

こんばんは、ダンです。

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

ってわけで素数を求める！
１０億まで！

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

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

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

とりあえずchar型配列1bitに１桁対応させよう！
そして偶数除外しよう！
そしたら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億までの素数の数でぐぐったけど、同じ数でした。
っということでとりあえず一安心。

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

はい、18秒！

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