Arantium Maestum

プログラミング、囲碁、読書の話題

素数

Alex Martelli版エラトステネスの篩をClojureで書いてみた

素数算出アルゴリズムで最も有名なものは多分エラトステネスの篩だろう。発見した素数の倍数を消していく(篩にかけていく)ことによって、残った数の中で最小のものが素数だとわかる。そのプロセスを繰り返していくことで、一定のn以下のすべての素数が効率…

Clojureで素数計算

Project Euler第三問から素数が関わってくる問題が始まる。 素数の計算といえば有名どころはエラトステネスの篩だろう。ただ、Haskellで間違った実装が数十年に渡って教えられていたりと、とくに無限に続くようなSieveはなかなかコードが理解しにくい。 Siev…