1.Brute force method


ある数 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番目の素数を与える関数、というようなものは、今のところ知られていない。
従って上限無しで、どんどん試しの割り算を進めていきたい時は、

できるだけ多く素数を含むような数列を利用する

という方法をとるのが一般的である。

その1

まず、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

その2

上の方法で、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

その3

ならば、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桁程度しかのびない。

よって、もっと大きな数を素因数分解する(もっと大きな素因数を見つける)ためには、
もっと別の方法でアプローチしなければならない。


この章の目次

E-mail : kc2h-msm@asahi-net.or.jp
三島 久典