投稿者 スレッド: 素朴な方法による素因数分解  (Read 1152 times)

工事中

  • ゲスト
素朴な方法による素因数分解
« 投稿日:: 2020年 4月 08日 , 午後 03:44:50 »
素朴な方法による素因数分解
サンプルプログラムについて、素朴な方法による素因数分解について、
data コマンドで、素数を2から29989までで、定義しておいて。
まではわかるのですが、例えば8なら
*2^3
なんで、*始まりで、出力するのかわかりませんが。例えば
8 =
2^3
ならわかりますが。
8 =
*2^3
とするのかがわかりません。

これは、先生は失望なされると思いますが。

'
'素朴な方法による素因数分解
'
MaxPrime = 29989
 
 Input "n"; n
 print n ;" = "

までは、素数の最大値を29989としたとき、 input文で入力した、数nを、2から29989までの全素数で、
data数で圧倒されそうですが。正直すごいと思いました。

print文で、nは入力した値だと思います。
n=素因数分解で表しているんだなとまではわかります。
以下全然わかりません。
主ブロックで、dataから、参照して、いろんな組み合わせを、試しているんだなと思います。
その繰り返しの中で、素数、と、指数とで、入力した値、nを表しているのだと思います。
当方、windows 10で試していますが、物凄いスピードで演算結果が出てきます。

余談が過ぎましたが、このプログラムを開設していただけないでしょうか?

takeuchi

  • 管理人
  • *****
  • 投稿: 93
Re:素朴な方法による素因数分解
« Reply #1 投稿日:: 2020年 4月 09日 , 午後 02:16:48 »
こんにちは,

> 8 =
> 2^3
> ならわかりますが。
> 8 =
> *2^3
> とするのかがわかりません。

これは単なる手抜きです。
6=
2
3
と出力するよりも,
6=
*2
*3
の方が良い?と思ったからです。本当は
6=
2
*3
の方が良いかもしれません。ここでは表示は簡略で済ませています。このプログラムは比較的大きな数も
簡単にプログラムで因数分解できるという例です。例えば
12345678901の入力に対しては,

12345678901 =
*  857
*  14405693

を出力します。

MaxPrime = 29989

は,このプログラムにData文で書かれている素数の最大数です。

素因数分解の方法は素朴に小さな数から割っていって因数を見つけています。
素数で割っていくのが最も効率的なので,可能な範囲でそれを実行します。
つまり,MaxPrime 以下の素数で割っていって,それでも不足の場合は奇数で
割っていきます。

    if p < MaxPrime then Read p else p=p+2

は,p < MaxPrime なら,Data文から次の素数を読み取り,そうでなければ次の奇数を
素因数の候補としています。

入力した数をnとしていますが,素数pで割り切れた場合,商q=n/pを改めてnと置いて,それを
また素数で割っていきます。割り切れた回数がiです。i=0なら割り切れないので何もしないで次の
因数候補のpで割ります。i=1なら,その素数を出力し,i>1なら,冪の形p^iで出力します。
(奇数で割っていっても実際に割り切れることがあるのは素数の場合のみです。)
この場合分けが,

    Select Case i
       Case 0
       Case 1
          print "* ";p
       Case else
          print "* ";p;"^";i
    End Select       
です。

n=1になってしまえば,分解が終わり,p*p>n になったら,nが実は素数
であり,これでも分解が終わります。

while (n > 1) and ( p*p <= n)
...
wend

となっているのはこのことからです。

プログラムの内容を詳しく理解するには,小さなnについて手計算とプログラムの
手順を比較してみるのも一つの方法です。計算途中の変数の値を知るには,
その該当部分に適宜Print文を追加して動かします。
例えば,
while (n > 1) and ( p*p <= n)
のすぐ下に
Print "n=";n
を追加して動かすとnの変化の様子が分かります。

なお,tbasic特有の関数 PFactorを使うともっと簡単に同様のプログラムが作れます。