エラトステネスのふるいで素数を求める

C:\DATA\Java2\Dos>java Matsosu
   2   3   5   7  11  13  17  19  23  29
  31  37  41  43  47  53  59  61  67  71
  73  79  83  89  97
 -- Press any key to exit (Input "c" to continue) --

「エラトステネスのふるい」を応用して 100 までの素数を求めます。
素数は一行に10件ずつ表示しています。
素数を求めるよりも、こちらの方が難しいかも知れません。

前田稔の超初心者のプログラム入門

プログラムの作成

  1. メモ帳などでタイプして Matsosu.java の名前で保存して下さい。
        // エラトステネスのふるいで素数を求める  前田 稔
        public class Matsosu
        {   public static void main(String[] args)
            {   int     t[] = new int[100];     //配列の生成
                int     i,j;
    
                for(i=2; i<100; i++)    t[i]= i;
                for(i=2; i<8; i++)
                    for(j=i+i; j<100; j+= i)    t[j]= 0;
                for(i=2; i<100; )
                {   for(j=0; j<10 && i<100; i++)
                        if (t[i]!=0)
                        {   if (i<10)   System.out.print("   " + i);
                            else        System.out.print("  " + i);
                            j++;
                        }
                    System.out.println("");
                }
            }
        }
        
  2. Matsosu.java をコンパイルして Matsosu.class を作成して下さい。
    class オブジェクトを実行して下さい。
    コンパイルの詳細は Java を動かす を参照して下さい。
  3. ページ先頭の画面が表示されたら完成です。

エラトステネスのふるい

素数を求める「エラトステネスのふるい」の説明です。
エラトステネスはギリシアの博物学者で素数を見つける方法(エラトステネスの篩ふるい)を案出しました。
また地球の形を球体と考え、その全周を推定しています。
年代は古く「紀元前 276 頃〜紀元前 195 頃」で、もちろんコンピュータの面影もありません。
従って、これからの説明もコンピュータを意識したものではありません。
  1. step 1: 2からnまでのすべての整数を「ふるい」に入れる。
  2. step 2: 「ふるい」に入っている数の中で最小の数を取り出し「素数」に加える。
  3. step 3: この数の倍数を全て「ふるい」から除く。
  4. step 4: 「ふるい」が空になるまで、step 2,3 を繰り返す。


プログラムの説明

  1. 100以下の要素を求めるために配列を定義して2〜99の値を格納します。
    配列の割り当ては 配列を割り当てる を参照して下さい。
        {   int     t[] = new int[100];     //配列の生成
            int     i,j;
    
            for(i=2; i<100; i++)    t[i]= i;
        
  2. 2〜7までの倍数をテーブルから取り除きます。
    これでテーブルに残った数は全て素数になります。
  3. 何故7までで良いかと言うと、本当は sqrt(100)=10 で10まで消し込めば良いのですが、 10は2の倍数、9は3の倍数、8は2の倍数で、実質的に7で良いことになります。
    sqrt(100) の根拠は、もし a を割り切る整数 n が存在すると a = n * m で、n と m のどちらかは sqrt(a) より小さい値になるからです。
        for(i=2; i<8; i++)
            for(j=i+i; j<100; j+= i)    t[j]= 0;
        
  4. テーブルに残った素数を一行に10件ずつ表示します。
        for(i=2; i<100; )
        {   for(j=0; j<10 && i<100; i++)
                if (t[i]!=0)
                {   if (i<10)   System.out.print("   " + i);
                    else        System.out.print("  " + i);
                    j++;
                }
            System.out.println("");
        }
        

【演習】

課題

配列が10個の場合を想定してプログラムをトレースして下さい。

超初心者のプログラム入門(Java2)