素数の一覧を表示する

前田稔(Maeda Minoru)の超初心者のプログラム入門

【エラトステネスのふるい】

1. 配列を使って、エラトステネスのふるいで 1000 以下の素数を求めて表示します。
   
2. 素数とは「２以上の１と自分自身以外に約数を持たない整数」のことを言います。
   例えば１３は、２でも３でも・・・７でも割り切れず、１３を割りきることのできる数は、 １と１３だけなので１３は素数です。
   １５は「３*５＝１５」で３と５で割り切れるので素数ではなく合成数です。
   
3. 「エラトステネスのふるい」の説明です。
   エラトステネスはギリシアの博物学者で素数を見つける方法(エラトステネスの篩(ふるい))を案出しました。
   また地球の形を球体と考え、その全周を推定しています。
   年代は古く「紀元前 276 頃～紀元前 195 頃」で、もちろんコンピュータの面影もありません。
   従って、これからの説明もコンピュータを意識したものではありません。
   この考え方をコンピュータに適合するようにプログラムして下さい。
   
   1. step 1: ２からｎまでのすべての整数を「ふるい」に入れる
      
   2. step 2: 「ふるい」に入っている数の中で最小の数を取り出し「素数」に加える。
      
   3. step 3: この数の倍数を全て「ふるい」から除く。
      
   4. step 4: 「ふるい」が空になるまで、step 2，3 を繰り返す。
      
4. この考え方に基づいて 1000 までの素数を表示して下さい。
   

プログラムの説明

1. プログラムの構成を考えて見ましょう。
   tbl が１０００以下の素数を求める配列です。
   ここに２～１０００の値を格納します。(０と１は素数で無いので無視)
   

   int[] tbl = new int[1000];

   1. テーブルに格納されている最初の値「２」は素数です。
      素数が見つかれば、その倍数をテーブルから取り除きます。
      ２のときは「４，６，８，・・・１０００」を取り除きます。
      プログラムでは、取り除く代わりにゼロを格納します。
      
   2. 次に見つかる値は「３」なので「６，９，１２，・・・９９９」を取り除きます。
      
   3. ４は２の倍数として取り除かれているので、次の値は「５」なのでその倍数を取り除きます。
      
   4. 幾らまで調べれば良いのでしょう。
      今回求めるのは１０００までなので、１０００の平方根(約３３)まで調べればＯＫです。
      何故ならば、もし１０００を割り切る値「ｎ*ｍ＝１０００」が存在するならば、ｎとｍのどちらかは ３３より小さいからです。
      
2. 説明したことをヒントにしてプログラムを作成して下さい。
   
3. １０００までの素数の数は１６８個です。
   「１６８個の数字を一行に１０個ずつ」並べて表示してみましょう。
   

前田稔(Maeda Minoru)の超初心者のプログラム入門