キンサクプログラマー

お金儲けと技術のメモ

毎日アルゴリズム(第1日目)エラトステネスの篩

暇なので毎日アルゴリズムを勉強することにした。1日で終了しないことを目標に頑張ろうと思う。
いつか、ホットエントリーにのるその日まで・・・

エラトステネスの篩

エラトステネスの篩とは素数を見つけるアルゴリズムN以下の素数を全部みつけることができる
第1日目にふさわしくとっても簡単。

アルゴリズム

  • 2〜Nまでの配列を準備
  • 2の倍数を消す
  • 3の倍数を消す
  • 4のば・・・ 4は消えているね〜
  • 5の倍数を消す
  • Nの平方根までやって、残ったのが素数

平方根までしか計算しなくて良い点が、計算時間削減の肝。
プッチ神父もびっくり

コード

Pythonを勉強しているので、Pythonで書いてみた。
github.com