Category Archives: 整数・自然数・素数

VBScriptで素因数分解

ドラマ『探偵ガリレオ』
シーズン2より後に見てしまいました。湯川学のように徹底して頭の中が物理中心って人いいですね。自然とそういう人種と仲良くなりやすいのか、現実にも周囲にたくさんいる気がします。毎回楽しく勉強できるガリレオシリーズですが、最終話で素因数分解がでてきました。ちょうど手元で読んでる「数学ガール」(結城浩 著)にも約数のことが出てきたので、おさらいを兼ねてプログラミングしてみます。
まずは、紙と鉛筆だけで計算してみます。むむっ、普段全部高性能な電卓で計算するので、いざ素因数分解しようと思うと、それ何状態です。あー確か最初は2で割るんだな、と思い出して、こんな計算をしました。

100の素因数分解(間違い)

2 )___100____ … 0
2 )____50____ … 0
2 )____25____ … 1
2 )____12____ … 0
2 )____06____ … 0
2 )____03____ … 1
2 )____01____ … 1

おっと、職業柄、2進数を求めていたよ。これは素因数分解ではありません。正しくは割り切れないときは、次の素数で計算しなければなりません。

100の素因数分解

2 )___100____
2 )____50____
5 )____25____
5 )_____5____
1

100 = 2 x 2 x 5 x 5 となります。

では素因数分解スクリプトをVBScriptで作ってみます。いきなりソースコードです。
(divsor.vbs)

nn=inputbox("正の約数を求めたい自然数は?(100まで)")

primes=Array(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97)

ind=0
out=""

while nn <> 1
	if (nn mod primes(ind)) = 0 then
		out=out&primes(ind)&" )___"&_
		nn&"_____"&VbCrLf
		nn = nn / primes(ind)
	else
		ind = ind + 1
	end if
wend

msgbox out

100までなのは、primesに定義している素数が100までの素数だからです。そういえば、素数に関しては、以前マインクラフトで素数階段を作りましたが(Minecraft Pi EDで素数階段を上る(その3)) 実際にゲーム空間で素数階段を上るととても感慨深い気持ちになります。素数を用いる素因数分解も計算しててとても面白いです。

上記スクリプトを実行してみましょう。


100までの好きな自然数を入力してクリックすると、

計算結果が表示されます。左に縦に並んでるのが約数ですね。