素数判定

　自然数入力が素数であれば、なければを返す。

　AKS素数判定法の元となった、フェルマーテストの変法を素直に用いる。すなわち

　, が互いに素な自然数とする。このとき任意の自然数について：

のとき、且つそのときに限り、は合成数である       (必要十分条件)

　これより、とした上でにと素な素数(2,3,5,7,11,...)を一つ選び、に, と異なる自然数を選び、

を判定すれば、が素数であるか否かが判明する

　ここでまたはが大きい場合に、比較的高速に計算する方法が存在する。

(w)

Prepared: 20150723

Updated: 2015----

戻る