[ サイトマップを見る ]

今日学ぶこと

ふたつの数の最大公約数をもとめることができる

約数

約数とは，ある数を割り切ることができる数のことをいいます。

例えば，1 は 1 で割り切れます。1 の約数は 1 です。

2 は 1, 2 で割り切れます。2 の約数は 1 と 2 です。

3 は 1, 3 で割り切れます。3 の約数は 1 と 3 です。

4 は，1, 2, 4 で割り切れます。4 の約数は 1, 2, 4 です。

最大公約数

最大公約数とは，ふたつの数の約数のうち，同じ数で一番大きい数のことをいいます。

上の例で言えば，1 と 2 の最大公約数は 1 です。1 の約数は 1，2 の約数は1, 2 です。ふたつの数のうち，共通で一番大きい数は 1 です。この場合，1 と 2 の最大公約数は 1 になります。

さきほどの例では 1 と 2 の最大公約数を求めました。１の約数の個数は１つ，2の約数の個数は２つですから，最大公約数もすぐ求めることができました。1024 と 320 の最大公約数を求める場合は，ちょっと計算がたいへんそうです。

1024 の約数は，1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024。

320 の約数は，1, 2, 4, 5, 8, 10, 16, 20, 32, 40, 64, 80, 160, 320。

このうち，共通している約数は 1, 2, 4, 8, 16, 32, 64。

一番大きい数は 64です。これが最大公約数です。

ユークリッドの互除法

1024 と 320 の最大公約数を求める簡単な方法があります。その方法に名前がついており，ユークリッドの互除法といいます。

1024 を 320 で割ると，商が 3，余りは 64 です。

$$
1024 = 320 \times 3 + 64
$$

次に 320 を 64 で割る場合を考えます。さきほど割る数だった 320 を割られる数に，さきほど余りだった 64 を割る数として考えるわけです。

$$
320 = 64 \times 5
$$

320 を 64 で割ると，商が 5，余りは 0 です。

余りが 0 になった段階で，計算をやめます。割る数だった 64 が最大公約数となります。

ユークリッドの互除法の手続き

これまでは具体的な数を使って考えてきました。ここからは変数を使って一般化して考えていきましょう。手続きをフローチャートにしてみました。

a と b の最大公約数を求める手続きはつぎのとおりです。

ステップ１

c に a を，d に b を代入します。

ステップ２

c を d で割ります。c は次のように書けます。

$$
c = d \times p + r
$$

ここで p は商，r は余りです。

r = 0 の場合，計算は終わりです。最大公約数は d です。

余りがゼロ以上の場合は計算を進めます。

ステップ３

c にd を，d に r を代入します。

ステップ２に戻ります。

Python でコードを書く

さきほどのフローチャートをもとに最大公約数を求めるコードを書いてみましょう。次のように書くことができます。

#greatest common divisor

import sys
import math

# step 1

a = int(sys.argv[1])
b = int(sys.argv[2])

if a>b:
    c, d = a, b
else:
    c, d = b, a

while True:

    #step 2
    r = c % d
    print(c,end="")
    print("%",end="")
    print(d)
    if r == 0:
        print(d)
        break
    c, d = d, r

print(math.gcd(a,b))

ちなみに，自分で書かなくても，math には gcd() という関数が用意されています。gcdはgreatest common divisorの略です。一番最後の行に gcdを使った例を書いています。

関連する書籍

[ サイトマップを見る ]