素数判定・素数列挙を行う主なアルゴリズムをPython 3で実装してみた：試し割り法からMiller-Rabin素数判定法まで
競技プログラミングにおいては、素数判定（ある自然数が素数か否かを判定する処理）あるいは素数列挙（ある範囲に含まれる素数を列挙する処理）が求められることがあります。そこで、本記事では、素数判定・素数列挙のための代表的アルゴリズムを挙げるとともに、私がそれらをPython 3で実装したものを示します。同様の事項について書かれた記事はすでに多数ありますが、ここでは学習の記録を兼ねて自分なりにまとめておきます。
きっかけ
最近、私は競技プログラミング用のライブラリを作成し始めました。とはいうものの、体系的に作成しているというよりも、むしろ、問題演習を通じて新たなアルゴリズムや技法に出会う度に、それをライブラリに追加しているというところです。しかしながら、素数判定・素数列挙にまつわる主要なアルゴリズムについては、まとめて実装してライブラリに加えました。その主な理由としては次の三つが挙げられます。第一の理由は、先ほど述べたように、競技プログラミングにおいて素数に関する処理が必要となることは、決して稀ではないということです。それゆえ、あらかじめ素数判定・素数列挙のライブラリを用意しておくことは重要であるといえます。第二に、競技プログラミングにおける数学的事項のうちで、素数をはじめとする数論的事項は私にとってどちらかというと馴染みのあるものであるということが挙げられます。たとえば、競技プログラミングではグラフ理論とそれにまつわるアルゴリズムがよく利用されますが、私がグラフ理論を知ったのは競技プログラミングを始めてからです。これに対して、素数や約数・倍数といった数論的事項には、競技プログラミング以前の学習で触れる機会がありました。第三の理由としては、どういうわけか素数は興味深いものであると感じるということがあります。Twitterでも言及しましたが、私は数学が得意でもなければ、大好きであるというわけでもありません。しかしながら、なぜだかわからないのですが、素数やそれを扱うアルゴリズムには心惹かれるものを感じるのです。もしかすると、数年前に読んだ『虚数の情緒』という本の影響によるものかもしれません。
注意事項
主な素数判定・素数列挙アルゴリズムとその実装例
試し割り法
試し割り法は、素数判定用の単純な決定的アルゴリズムです。この方法では、素数判定の対象である自然数を2から
までの自然数で割ります。割り切れるものが一つも存在しなければ
は素数であり、さもなければ
は素数ではありません。この手法の時間計算量は
です。
Eratosthenesの篩と区間篩
Eratosthenes（エラトステネス）の篩は、未満の素数を列挙するのに利用できる決定的アルゴリズムです。その各ステップはwikipedia:en:Sieve_of_Eratosthenesに詳述されています。同記事によると、この手法の時間計算量は
であるといいます。これは自然数
一個の素数判定に要する時間計算量ではなく、
未満の全素数の列挙に必要なそれであることに注意してください。以下の実装では、Python標準ライブラリのarrayを用いて、空間計算量の削減を図っています。
この方法の亜種として、区間篩というものがあります。これは、区間の素数表を用いて、
の素数を列挙するという方法です*1。
Miller-Rabin素数判定法
Miller-Rabin（ミラー–ラビン）素数判定法は、与えられた自然数の素数判定を行うためのアルゴリズムです。ここまで述べてきたアルゴリズムとは異なり、この手法は確率的アルゴリズムあるいは乱択アルゴリズムです。Miller-Rabin素数判定法では、
]の範囲から擬似乱数を用いて自然数
をランダムに選び、これを用いた判定を行うという操作を
回行います*2。wikipedia:ミラー–ラビン素数判定法によれば、この方法の時間計算量は
であるといいます。また、同記事によると、この方法で合成数を誤って素数と判定する確率は最大で
であるといいます。
自然数があまりにも大きく、上述の手法では制限時間内にその素数判定ができないときに、Miller-Rabin素数判定法の利用を考えるとよいでしょう。とはいえ、このアルゴリズムを使わなければならないような問題は、めったに出されないようです*3。
感想とまとめ
素数判定・素数列挙のアルゴリズムについてはかねてから名前程度は知っていましたが、（文献のコード例を参照しながらではありますが）自分でその実装コードを記述するのはおそらくこれが初めてのことでした。今後は問題演習を行いながら、数論にまつわるものにとどまらず、競技プログラミングで必要となる種々のアルゴリズムを実装したいと考えています。
また、この記事では実装したコードの性能評価（例：計算速度の実測）は行いませんでしたが、できれば後日やってみたいと考えています。
*1:『プログラミングコンテストチャレンジブック』（第2版）p.113によります。
*2:wikipedia:ミラー–ラビン素数判定法によります。
*3:『最強最速アルゴリズマー養成講座』p.409によります。ただし、以前にyukicoderにおいてMiller-Rabin素数判定法の利用が想定解である問題が出されたことがあります。
