最大公約数と最小公倍数
ってなんだっけ？
と言う小学生レベルの算数も怪しい私自身に説明するつもりで書く
・最大公約数
24 36とあった時にどっちでも割れる数で一番大きいもの
例えば共通で割れるものとして2, 3, 4, 6, 12とかやっていって
この場合は12が一番大きいので12が答えとなる
大体はすだれ算を使ってやる
こんなやつ↓
| 2 | 24 | 36 |
|---|---|---|
| 2 | 12 | 18 |
| 3 | 6 | 9 |
| 2 | 3 |
縦に2 * 2 * 3とやれば最大公約数が求められる
・最小公倍数
24 36とあった時どちらも足していって最初に共通の数字が現れたもの
以下の場合は72が共通の数字が現れるので72となる
| 24 | 48 | 72 |
|---|---|---|
| 36 | 72 | 108 |
すだれ算を使ってやった場合は
左と一番下を全て掛け合わせる
2 * 2 * 3 * 2 * 3 = 72
| 2 | 24 | 36 |
|---|---|---|
| 2 | 12 | 18 |
| 3 | 6 | 9 |
| 2 | 3 |
ここでユークリッド互助法と言うやり方がある
かっこいい名前がついているが方法としては簡単
最大公約数を求める場合はまず2つのうち大きい方を小さい方で割って剰余を求める
36 % 24 = 1 ...12
それを更に小さい方で割ってあまりを求める
24 % 12 = 2 ...0
あまりがゼロになった時点で割った数が最大公約数
次に最小公倍数だがこれはまず2つの数を掛け合わせる
36 * 24 = 864
次に出した積を最大公約数でわる
864 / 12 = 72
このユークリッド互助法を使ってpythonで最大公約数と最小公倍数を求めようとするとこうなった
l = input('Enter two number: ')
l = l.split()
a = max(l, key=int)
b = min(l, key=int)
a, b = int(a), int(b)
def do_gcd(a, b):
if a == b:
#return False
return a
while True:
if a % b == 0:
break
else:
a, b = b, a % b
return b
do_gcd(a, b)
c = do_gcd(a, b)
c = int(c)
print("最大公約数" ,c)
def do_lcm(a, b, c):
return a * b // c
do_lcm(a, b, c)
d = do_lcm(a, b, c)
print("最小公倍数" ,d)
Enter two number: 24 36
最大公約数 12
最小公倍数 72
スペース区切りで数字を2つ入れるとそれぞれ結果を返してくれる
ちなみに結構苦労して書いたが、mathを使うと最大公約数をわずか2行で求められることが判明^^;
便利なものはどんどん使っていこうと言う教訓であった
import math
math.gcd(24, 36)
12
-20210618 追記
以下のように書けばもっと簡単に書けるよとユーザさんよりご指摘いただく。
修正点① そもそも引数をmaxとminで判定するのは不要
修正点② 2つの引数が同じだった場合の最大公約数はFalseじゃない
修正点③ while Trueで無闇に無限ループ回さなくていいじゃんね
私には絶対思いつかないコードである(苦笑)
(@StrawBerryMoonさん有益な情報ありがとうございます。)
いただいたアドバイスを元に修正したコードは以下の通り
l = input('Enter two number: ')
l = l.split()
a, b = int(l[0]), int(l[1])
def do_gcd(a, b):
while b != 0:
a, b = b, a % b
return a
do_gcd(a, b)
c = do_gcd(a, b)
c = int(c)
print("最大公約数" ,c)
def do_lcm(a, b, c):
return a * b // c
do_lcm(a, b, c)
d = do_lcm(a, b, c)
print("最小公倍数" ,d)