はてなブックマーク

競技プログラミングにおいては、素数判定（ある自然数が素数か否かを判定する処理）あるいは素数列挙（ある範囲に含まれる素数を列挙する処理）が求められることがあります。そこで、本記事では、素数判定・素数列挙のための代表的アルゴリズムを挙げるとともに、私がそれらをPython 3で実装したものを示します。同様の事項について書かれた記事はすでに多数ありますが、ここでは学習の記録を兼ねて自分なりにまとめておきます。 きっかけ 注意事項 主な素数判定・素数列挙アルゴリズムとその実装例 試し割り法 Eratosthenesの篩と区間篩 Miller-Rabin素数判定法 補足 感想とまとめ 参考文献 きっかけ 最近、私は競技プログラミング用のライブラリを作成し始めました。とはいうものの、体系的に作成しているというよりも、むしろ、問題演習を通じて新たなアルゴリズムや技法に出会う度に、それをライブラリに追加し

3月25日14時30分（日本時間）から丸3日間にわたり、HackerRankにてLambda Calculi - March 2016という関数型言語縛りのプログラミングコンテストが開催され、私はそれに参加しました。Lambda Calculiを冠するコンテストは以前にも何度か開かれていたようですが、私にとってはこれが初めての参加でした。 コンテストの概要 私の結果および取り組み 第1問：Functions or Not? 第2問：Compute the Perimeter of a Polygon 第3問：Compute the Area of a Polygon 第4問：Concave Polygon 第5問：Tree manager 第6問：Fighting Armies 第7問：Simplify the Algebraic Expressions 感想 おわりに コンテストの概要