AOJ 0009 Prime Number

問題

6 桁以下の正の整数 n を入力し、n 以下の素数がいくつあるかを出力するプログラムを作成して下さい。ただし、素数とは 1 と自分自身でしか割り切れない正の整数のうち 1 をのぞいたものをいいます。例えば 10 以下の素数は、2, 3, 5, 7 です。

解答

  1. エラトステネスの篩で素数を計算
  2. 入力の数を辞書に登録
  3. 素数0から1000000まで素数の累積を数える
  4. 辞書に登録した数に達したらそこまでの累積を連想配列に保存
  5. 入力の順に累積の素数を出力

gist8bd3f22e2f970b1a2899

追記

素数だけの配列を用意して,入力の数以下の位置をバイナリサーチすればよかった.(バイナリサーチ結果の位置が素数の累積と対応する).そっちの方がエレガントに書ける.