Special Lesson 3 - 約数，倍数の扱い

　「BがAの約数である」ことは，Mod演算子を用いてもよいですが，他にも以下のように表されます。

A=Int(A/B)*B

　なぜなら，AがBで割り切れるなら A/B=Int(A/B) であり，これにBをかけたものがAに一致する一方，AがBで割り切れないとき A/B≠Int(A/B) であり，これにBをかけたものはAに一致しないからです。

　下のプログラムは，約数の判定をします。

#prompt
Dim A As Double, B As Double
Input A
Input B
If A=Int(A/B)*B Then
    Print B;"は";A;"の約数です。"
ElseIf B=Int(B/A)*A Then
    Print A;"は";B;"の約数です。"
Else
    Print B;"は";A;"の約数でありません。"
    Print A;"は";B;"の約数でありません。"
End If

<実行例>

? 14
? 7
7 は 14 の約数です。

? 5
? 35
5 は 35 の約数です。

? 20
? 8
8 は 20 の約数でありません。
20 は 8 の約数でありません。

問１９
　数列 {a_n} は，次の形で定義されている。

a_n = (n² + 2 が持つ約数の数) (n = 1, 2, 3, ...)

　例えば，以下のような値になる。

n = 1	1² + 2 = 3	3 の約数は 1, 3	a₁ = 2
n = 2	2² + 2 = 6	6 の約数は 1, 2, 3, 6	a₂ = 4
n = 3	3² + 2 = 11	11 の約数は 1, 11	a₃ = 2
n = 4	4² + 2 = 18	18 の約数は 1, 2, 3, 6, 9, 18	a₄ = 6

　この数列の，初項から第２０項までを表示するプログラムを作成せよ。（ヒント：最初に n² + 2 を計算し，1 からその数までの間に約数となるものがいくつあるかを調べる。）

　次に，有名な「ユークリッドの互除法」という最大公約数の求め方を述べます。
　２つの整数の最大公約数を求めますが，この２数を a, b とします。
　もしこの時 a が b の倍数であるかあるいはその逆であれば，その小さい方が最大公約数と確定します（当たり前）が，そうでなければ a > b とし（違えば入れ替えればよい），a, b の公約数が c であると仮定します。この場合，a = a₁c, b = b₁c とおくことができるので，辺々引くと

a - b = c(a₁ - b₁)

　すなわち，a - b もまた c を約数に持ちます。
　この時 min{a, b} と a - b の間で同様の判定をします。（min{a, b} は a と b の小さい方を示す）そうしてもし一方が他方の倍数であれば，その小さい方がこの２数の最大公約数というだけではなく，最初の a と b との最大公約数でもあるのです。

　この繰り返しで，一方が他方の倍数になった場合に，その小さい方を最初の a と b との最大公約数であるという形で最大公約数が得られます。

実際には，数を１回ずつ引かず（a - b のように），a - b < b となるまで引く（すなわち，余りを取る）ことで計算速度を上げています。

#prompt
Dim A As Double, B As Double
Dim C As Double ' ２値を交換するため。
Dim R As Double

Print "最大公約数を求める"
Input A
Input B
If A<B Then ' A>=B にしておきたいので，もし逆なら交換する。
    ' ２値を交換する際の定石。１つ余分に変数が必要なことに注意。
    C=A
    A=B
    B=C
End If

While A<>Int(A/B)*B ' もしAがBの倍数ならばループを抜ける（そうでないときループに入る）。
    R=A Mod B ' 余りを計算（A - B の代わり）。

    ' 次は B と R で判定する。このために B → A ，R → B と置き換える。
    A=B
    B=R
Wend

Print "最大公約数は:";B

問２０
上のプログラムを書き換えて，A と B の最小公倍数を求めるプログラムを作成せよ。（ヒント：A と B の最小公倍数を P，最大公約数を Q とすると，P = A×B÷Q）

戻る