■アルゴリズムの重要性■

アルゴリズムとはわかりやすくいえば計算方法のことで，同じ計算結果を得るためにも効率のよい方法が色々考案されてきた．

素数を求める

例として，2〜1000000未満の数から，すべての素数をプリントするプログラムを作成せよ．

定義どおりの方法

素数とは，1を除く自身より小さなすべての素数で割り切れない数のことである．これを求めるためには，2〜1000000までループしながら，その数が2〜自分自身-1までの2重ループして，割り切れるかどうか確認すればよい．どの数でも割り切れなければ素数だとして数をプリントする．

割り切れるかどうかは，剰余演算子を使ってあまりが0かどうかで判断できる．

エラトステネスのふるい

こちらは，あらかじめ配列に2〜1000000までの数を用意しておき，2からスタートする．2は素数であることは明らかなので，2をプリントする．そして配列中の2の倍数を消去する．次にひとつ大きな数を調べる．消去されていなければ素数なのでプリントする．そしてまたその数の倍数を消去する．これを最後まで繰り返せばよい．

演習課題3

(1)定義どおりの方法と，(2)エラトステネスのふるいの2種類で，1000，5000, 10000，50000, 100000, 500000, 1000000の7通りの数までの素数を全部求める時間を計測し，記録せよ．それをCalcでグラフにして比較せよ．

時間の計測

実行時間の計測は，簡単には次のように行えばよい．

 long start = System.currentTimeMillis();//処理開始時間

    素数を求める計算処理

 long stop = System.currentTimeMillis(); //処理終了時間記録		
	System.out.println("計算時間= " + (stop - start) + " ミリ秒");

nが増えた時にどうなるのか

現代の計算機は十分速いものの，このように素数を求める最大数のnのように，どんどん大きくなった時にアルゴリズムによる差が効いてくる．画像処理の場合，640×480画素のデータと1280×1024画素のデータでは画素数が大きく異なり，アルゴリズムを少しでも工夫しないとならない．