AOJ ALDS_1_C: PrimeNumbers

今日はAOJのALDS_1_Cの問題を解きます。 問題は以下のリンク先にあります。

Prime Numbers | Aizu Online Judge

問題は入力の中にある素数の個数を求めるものです。 まず、素数について簡単におさらいしましょう。 素数とは、約数として1とその数自身のみしか持たない自然数のことですね。

上記のことから与えられた整数xに対する簡単なアルゴリズムは、xをfor文を用いて2~x-1の数で割ってみるということが考えられます。しかし、これではxが大きくなるにつれて計算量も大きくなってしまいます。

ここではもう少し工夫して問題を解いていきましょう。 皆さんも考えてみてください。 解答は以下のようになります。

ここではエラトステネスの篩というアルゴリズムを用いました。 エラトステネスの篩の特徴は以下のようになります。

1. 2以上の整数を考える
2. 最小値の2を残し、その倍数を消去する
3. 次に残った値の最小値の3を残し、その倍数を消去する
4. 以下は同様に5, 7, 9と繰り返す

また、問題や問題のサイズによっては整数を配列に保持しておくことで、プログラムがより良くなります。