Pythonで最小公倍数、最大公約数を計算する

Pythonで最小公倍数と最大公約数を計算します。いずれも、簡単に計算することができる関数がありますが、その前に自作で関数を作成します。とりわけ、3つ以上の数に対する計算は複雑になります。

2つの数の最大公約数を計算する

最大公約数は2つの自然数で共通に割り切れる数をいい、英語ではgreatest common divisorといいます。

定義通りに最大公約数を計算する

小さい方から計算する

2つの変数aとbの最大公約数を計算します。2つの数のうち小さい方をlessとすると、最大公約数はlessよりも大きくなることはありません。そこで、最大公約数の候補をiとしてaとbを1からlessまでの自然数で割り算し、余りが0となる数のうち一番大きなものを求めればよいわけです。

  1. # 1 最大公約数の計算　小さい方から探す
  2. a = 48
  3. b = 36
  4. if a <= b:
  5. lesser = a
  6. else:
  7. lesser = b
  8. for i in range(1, lesser+1):
  9. if a % i == 0 and b % i == 0:
  10. gcd_l = i
  11. print(gcd_l)

12

  1. 4~5行目で、変数a,bのうち小さい数をlessに代入します。
  2. 8行目のfor文でiをlesserまでループし、9~10行目でaとbを割り切れることができれば公約数なので、gcd_lにその値を代入します。
  3. 結果的に、最後に見つかった公約数が最大公約数になります。

公約数を小さい数から探していくと、a、bがどのような数であってもforループを最後まで回す必要があります。

大きい方から計算する

前節とは逆に、最大公約数の候補として大きな方からループします。結果として、公約数が見つかった時点でプログラムが終了するので少しだけ効率的になります。

  1. # 2 最大公約数の計算 大きい方から探す
  2. a = 48
  3. b = 36
  4. if a <= b:
  5. greater = a
  6. else:
  7. greater = b
  8. for i in range(greater, 0, -1): # for i in reversed(range(1, greater+1)):
  9. if a % i == 0 and b % i == 0:
  10. gcd_g = i
  11. break
  12. print(gcd_g)

答えは同じ12です。

  1. 4行目以下で、aとbのうち大きい方を変数greaterに代入します。
  2. 最大公約数の候補をiとして、greaterから大きな順に公約数であるかを調べます。
  3. 最初に見つかったものが最大公約数なので、11行目のbreakでforループを抜け表示します。

大きな数から調べていくと、はじめに見つかった公約数が最大公約数になるので、そこでプログラムを終了させることができるので少し効率的になります。

ユークリッドの互除法

ユークリッドの互除法を使うと効率よく最大公約数を計算することができます。ユークリッド互除法では2つの整数を相互に割り算し、余りが0になるまで繰り返します。また、後で使いやすいようにgcd_eという関数にします。

  1. #3 ユークリッドの互除法による最大公約数を求める関数
  2. def gcd_e(a, b):
  3. while b:
  4. a, b = b, a % b
  5. return a
  7. gcd_e(48,36)

答えは同じ12です。

  1. 3行目の、while b:はwhile !=0:と同意です。余りが0になるまで繰り返すことを意味します。
  2. 4行目のa, b = b, a % bは、bをaに代入し、a % bをaに代入することを同時に行います。次と同じ意味です。

temp = a % b

a = b

b = temp

  1. 割り算の結果が0になったときのaが最大公約数として返り値になります。

答えは同じ12です。手計算をしても分かりますが、これまでの方法よりはるかに少ない手順で計算することができます。

再帰関数による最大公約数の計算

再帰関数によっても、最大公約数を計算することができます。

  1. #4 再帰関数により最大公約数を求める関数
  2. def gcd_r(a, b):
  3. if b==0:
  4. return a
  5. else:
  6. return gcd(b, a % b)
  8. gcd_r(128,84)

答えは同じ12です。

3つ以上の数の最大公約数

3つ以上の数の最大公約数

#2の方法によると、3つ以上の数の最大公約数を計算することができます。求めたい数は2以上いくつでも構わないようにするため、引数としてリストを渡します。

  1. #5 3つ以上の数の最大公約数を計算する
  2. def gcd_t(list_g1):
  3. for i in reversed(range(1, min(list_g1)+1)):
  4. for j in list_g1:
  5. if j%i!=0:
  6. break
  7. else:
  8. return i
  10. gcd_t([12,18,24]) 

6

  1. 3行目の1つ目のforループで最大公約数の候補をiとして、リストの中の最小の数から1つずつ減らしながらループします。
  2. 4行目の2つ目のループでは、リストをjとして1つずつ取り出し、iで割り算します。
  3. 全てのjで割り切れることができたら、そのiが最大公約数になるので7行目のbreakで2つ目のforループを抜け、else節に入り返り値とします。

リスト内包表記により3つ以上の数の最大公約数を計算

リスト内包表記を使うと、#5のプログラムを簡潔にすることができます。

  1. #6 3つ以上の数の最大公約数をリスト内包表記で計算する
  2. def gcd_l(list_g2):
  3. for i in reversed(range(1, min(list_g2)+1)):
  4. if any([j % i for j in list_g2]) == False:
  5. return i
  7. gcd_l([12,18,24])

前節と同じ結果となります。

2つの最大公約数を計算する関数を3つ以上の数に拡張

3つ以上の数の最大公約数を計算しようとすると、非常に複雑になります。そこで、2つの数の計算を、拡張することを考えます。最大公約数は対象となる数が共通する最大の約数なので、2つの数の最大公約数を計算して、この最大公約数と3つ目以降の数の最大公約数を順次計算すればよいわけです。このため、functionsモジュールのreduce関数を使います。

  1. #7 reduce関数を使った最大公約数の計算
  2. def gcd_e(a, b):
  3. while b:
  4. a, b = b, a % b
  5. return a
  7. import functools
  8. functools.reduce(gcd_e, [12,18,24])

  1. #4で作成したユークリッドの互換法を使った2つの数の最大公約数を求める関数を使います。このコードは#4を実行しておけば、書く必要はありません。
  2. 7行目でfunctoolsをimportして、8行目でこのうちのreduce関数を使用します。
  3. reduce関数は1番目の引数で指定した関数を、2番目のリストにある数を順次、適用していきます。つまり12と24の最大公約数を求め、この数と36との最大公約数を、さらに48との最大公約数を順次計算します。

最小公倍数の計算

2数以上の最小公倍数の計算

最大公約数から最小公倍数を計算

最小公倍数は、2数以上の共通の倍数で最も小さなものです。英語ではleast common multipleといいます。対象となる数が2つの場合（a,bとする）、最大公約数を計算することができれば、簡単に計算することができます。

$最小公倍数（lcm）=a×b/最大公約数（gcd）$

プログラムは次の通りです。

  1. #8 最大公約数から最小公倍数を計算する
  2. def lcm_e(a, b):
  3. return a * b / gcd_e(a, b)
  5. lcm_e(48,36)

144.0

このプログラムは、#7を実行していることが前提です。最小公倍数と最小公約数の関係を見れば明らかです。

再帰関数により最小公倍数を計算する

再帰関数を使うことにより最小公倍数を計算することができます。

  1. #9　再帰関数を使った最小公倍数の計算
  2. def lcm_r(a, b):
  3. remainder = a % b
  4. if remainder == 0:
  5. return a
  6. return a * lcm_r(b, remainder) / remainder
  8. lcm_r(48,36)

結果は同じです。

3つ以上の数字の最小公倍数を計算する

3つ以上の数をリストで引数として渡し、最小公倍数を返す極めて単純な関数を作成します。リストのうち最大の数（greatest）を1倍、2倍、i倍・・し、その数がリストの全ての倍数となる数が公倍数になります。最小公倍数なので、一番はじめはじめに見つかった数が最小公倍数になります。

  1. #10 最大の数の倍数から最小公倍数を計算
  2. def lcm(list_l):
  3. greatest = max(list_l)
  4. i = 1
  5. while True:
  6. for j in list_l:
  7. if (greatest * i) % j != 0:
  8. i += 1
  9. break
  10. else:
  11. return greatest * i
  13. lcm([12, 18, 24])

72

  1. 3行目でリストの最大値をmax関数で変数greatestに代入します。
  2. 4行目で最大の数の倍数に1を代入し、5行目でwhileループに入ります。while Trueはreturnとすると関数を抜けるまでループを繰り返します。
  3. 6行目のforループで、リストの数の全てについて、最大の数×iを割り切れることができるかを調べます。1つでも割り切れない場合には、iに1を足してbreak文でforループを抜け、次のiが公約数かどうかを調べます。
  4. forループの中で、greatest×iを全てのリストの値で割り切れることができたときは、else節に入り、その数を最小公倍数として返します。

結果的に原始的な方法の方が、応用が利くようです。

  1. #11　reduce関数を使った最小公倍数の計算
  2. def lcm_r(a, b):
  3. remainder = a % b
  4. if remainder == 0:
  5. return a
  6. return a * lcm_r(b, remainder) / remainder
  8. import functools
  9. functools.reduce(lcm_r, [12,18,24]) 

72.0

関数を使い、最大公約数、最小公倍数を計算する

Pythonの数学に関する関数で最大公約数、最小公倍数を計算します。

math関数

数学に関してはじめに思い浮かぶのがmathモジュールです。

  1. #11 mathモジュールで2つの数の最大公約数を計算する
  2. import math
  3. math.gcd(48, 36)

最大公約数として6が返ります。ところが、mathモジュールでは、3つ以上の数を引数に指定するとエラーとなり、最小公倍数を計算する関数が見当たりません。#8と同じ考え方で計算することを想定しているようです。

NumPy関数による最大公約数、最小公倍数の計算

NumPy関数には、最大公約数、最小公倍数を計算する関数が用意されています。

  1. #12 NumPyモジュールで最大公約数、最小公倍数を計算する
  2. import numpy as np
  3. print('gcd関数2つの最大公約数：',np.gcd(48, 36))
  4. print('lcm関数2つの最小公倍数：',np.lcm(48, 36))
  5. print('gcd.reduce関数3つの最大公約数：',np.gcd.reduce([12, 24, 36]))
  6. print('lcm.reduce関数3つの最小公倍数：',np.lcm.reduce([12, 24, 36]))

gcd関数2つの最大公約数： 12
lcm関数2つの最小公倍数： 144
gcd.reduce関数3つの最大公約数： 12
lcm.reduce関数3つの最小公倍数： 72

  1. 最大公約数はgcd関数、最小公倍数はlcm関数で計算します。ただし、これらの関数は2つの数までしか計算することができません。
  2. 3つ以上の数の計算をするときは、gcd.reduce,lcm.reduce関数を使います。この場合、引数はリストで渡します。

SymPy関数による最大公約数、最小公倍数の計算

SymPy関数には、最大公約数、最小公倍数を計算する関数が用意されています。

  1. #13 SymPyモジュールで最大公約数、最小公倍数を計算する
  2. import sympy
  3. print('gcd関数2つの最大公約数：',sympy.gcd(48, 36))
  4. print('lcm関数2つの最小公倍数：',sympy.lcm(48, 36))
  5. print('igcd関数3つの最大公約数：',sympy.igcd(12, 24, 36))
  6. print('ilcm関数3つの最小公倍数：',sympy.ilcm(12, 24, 36))

gcd関数2つの最大公約数： 12
lcm関数2つの最小公倍数： 144
igcd関数3つの最大公約数： 12
ilcm関数3つの最小公倍数： 72

  1. SymPyでは、最大公約数はgcd、最小公倍数はlcm関数で計算することができます。
  2. 3つ以上の数を指定する場合は、igcd、ilcm関数を使います。これらの関数はNumPyとは異なり、リストではなく単純に引数を指定します。