ある数 n の素因数を求める時、最も primitive な方法は、小さい数から順に割っていく方法である。
ubasic には、prmdiv() という組み込み関数があり、
234- 1 = 17179869183 以下の数について、最小素因数を返し、
最小素因数が見つからなかった場合は 0 を返す。
この関数を使ったプログラムは以下のとおり。
10 ' brute force method 1 20 input "n=";N 30 P=prmdiv(N):if P>1 then print P:N=N\P:goto 30 40 print N
ubasic には、nxtprm() という組み込み関数があり、ある数 p に対して p に最も近い( p より大きい)素数を返す。
(ただし、結果が、232= 4294967296 以上の時は 0 を返す)。
この関数を使ったプログラムは以下のとおり。
10 ' brute force method 2 20 input "n=";N 30 P=2 40 if N@P=0 then print P:N=N\P:goto 40 50 P=nxtprm(P):goto 40
さて、いずれの方法も、試しの割り算のための数に上限があった。
また、任意のiについてi番目の素数を与える関数、というようなものは、今のところ知られていない。
従って上限無しで、どんどん試しの割り算を進めていきたい時は、
できるだけ多く素数を含むような数列を利用する
という方法をとるのが一般的である。
まず、2で割り、割り切れなくなったら3で割り、以下、奇数で割っていく。
プログラムは以下のとおり。
10 ' brute force method 3 20 input "n=";N 30 P=2:gosub 70 40 P=3:gosub 70 50 P=P+2:gosub 70:goto 50 60 ' fnDiv(P) 70 if N@P=0 then print P:N=N\P:goto 70 80 return
上の方法で、3より大きい奇数について、3で割り切れるものは試行対象とする必要がないので除去する。
つまり、2×3=6以下の素数2、3、5についてはそのまま割り算。
6以上については, 6n+1, 6n+5 のみを割り算の対象とする。
プログラムは以下のとおり。
10 ' brute force method 4 20 input "n=";N 30 P=2:gosub 110 40 P=3:gosub 110 50 P=5:gosub 110 60 B=6:' =2*3 70 P=B+1:gosub 110 80 P=B+5:gosub 110 90 B=B+6:goto 70 100 ' fnDiv(P) 110 if N@P=0 then print P:N=N\P:goto 110 120 return
ならば、5の倍数も除去してしまおう。
2×3×5=30以下の素数については、そのまま割り算。
30以上については、
30n+1, 30n+7, 30n+11, 30n+13, 30n+17, 30n+19, 30n+23, 30n+29
を割り算の対象とする。プログラムは、上のプログラムを元にすれば容易に改造できるので省略。
私は以前、この2、3、5の倍数を除去する場合のプログラムを、ポケコンに入れて使っていた。
(プログラムはこちら。サイズが小さいので、じゃまにならない)。
ならば、7も11も……、というようにいくらでも効率化できるが、その分プログラムは長くなる。
それ以上に、この方法を押し進めていっても、試行対象の p の増え方は、素数定理より n log(n)のオーダなので、
あまり大きな p を検出することはできない(より詳しい議論はこちら)。
つまり、brute force method では分解できる数の上限があり(27桁ぐらい)、
かつその上限値は、計算機の速さが10倍になったとしても、2桁程度しかのびない。
よって、もっと大きな数を素因数分解する(もっと大きな素因数を見つける)ためには、
もっと別の方法でアプローチしなければならない。
前 | この章の目次 | 次 |
---|