prime method

Definition

　自然数入力xに対し、以下を満たすただ一つの数の組を求める

                            Where,     as primary number

                                          as integer >= 0

calculation

　素因数分解の方法はいくらでもあるが、ここで以下の通りとする：

　ある自然数が入力されたとき、

              1) が素数であるか否かを判定する

              2) が素数であればを出力して終了する

              3) が合成数であれば、適当な自然数aで割り切れるか否かを判定する

              4) がで割り切れれば、とで割り切れた回数を出力し、とする

              5) が元の入力自然数の平方根より小さくなれば、を出力して終了する

              6) が元の自然数より大きければ、1)へ戻る

　割る自然数aについて、xが奇数である(2の倍数でない)ことが分かっていれば、aは√x以下の奇数をスクリーニングするだけで良く、これにより全ての自然数を調べるより、計算のコストは半分に減る。さらにxが3の倍数でないことが分かれば、aとして3の倍数もスキップすることで計算コストはさらに1.5分の1となる。ここで自然数の集合Zを{2または3で割り切れない}とすると、Zの要素zi(i=1,2,3,...)をZの要素を小さな准に並べたものとするとき、z(i+1)-z(i)は周期的に変化するためコードを圧縮することにも寄与することとなる。

Prepared: 20150723

Updated: 2015----

戻る