26.1.6.11 素数表

エラトステネスのふるいは，以下のように実行します．

• 表を用意する
  表を配列で用意して，すべての要素(数)を初期化しておきます． 最初はすべての数が素数の候補なのです．
• 次の素数を見つける
  表の中で残っている数のうち最小のものは，自分より小さい素数の倍数ではなかったわけですから，素数であると分かります．
• 見つけた素数の倍数を消す
  これは単純なfor形式で実行できます．

プログラムを示します．

class Primes {
 public static void main(String argv[ ]) {
     int n=100;
     int i, k;
     int p[] = new int[n+1];
     for(i=1; i < p.length; i=i+1) p[i]=1; // 最初は全部が素数の候補
     for(i=2; i < p.length; i=i+1)
       if(p[i]==1){                            // iは素数
         System.out.print(i + " ");
         for(k=i; k*i <= p.length; k=k+1)   // 倍数を消す意味でゼロを書きこむ．
             p[i*k]=0;                         // 消すのはiの自乗から．
       }
     System.out.println();
 }
}

Primes.java (iso-2022-jp)

結果を示します．

iの倍数を消す際には，本来的にはiの2倍，3倍，と表から全て消していく必要があるのですが，例えばiが5だった場合にはiの2倍や3倍や4倍は，既にiが2や3の時に消去されています．従ってiの5倍，すなわちiの自乗から開始してもよいのです．もっと速くする方法も存在することでしょう．

配列の長さ(サイズ)は，配列名に".length"をつければわかります．この小さなプログラムでは101であるとわかりますが，".length"で書いておくと，配列のサイズが変更されてもプログラムのいろいろな所を書き直す必要がなくなります．