素数メモ

　暗黒通信団の素数表を眺めていて、なんとなく素数を計算させてみた。手元にテキストデータを用意しておくと色々加工できてよい。

暗黒通信団の素数表150000個についていたプログラム例をうまく走らせることができなかったのでちょっと修正。

#include <stdio.h>

// #define MAXN 2020000
#define MAXN 999999999

char n[MAXN];

int main(){
  for(long int i=0;i<MAXN;i++) n[i]=1;

  printf("2\n");

  for(long int i=3; i<MAXN;i+=2){
    if(n[i]){ printf("%ld\n",i);}
    for(long int j=i; j<MAXN;j+=i){
      n[j]=0;
    }
  }
}

　9桁までの素数をすべて求めるのに10分ぐらいだった。(MacBookPro、Core2Duo 2.53GHz)

2バイトの範囲内(0〜65535)に収まる素数
6542個　最後の数は 65521
13,084バイト必要

7桁までの素数について：
664579 個　最後の数は 9999991
4バイト単位で保存すると 2,658,316バイト必要
8桁までの素数について：
5761455 個　最後の数は 99999989
4バイト単位で保存すると 23,045,820バイト必要
9桁までの素数について：
50847534 個　最後の数は 999999937
4バイト単位で保存すると 203,390,136バイト必要

素数表150000個