最大公約数とは
皆さんご存じのように、最大公約数とは２つ以上の正の整数の共通の約数のうち最大の数のことです。
愚直に求める方法
2つの整数をa、bとします。aの約数のリスト、bの約数のリストをそれぞれ作成し、2つのリストに共通する要素の中で最大のものを求めます。
gcd1.py
def gcd(a, b):
a_div = []
b_div = []
div = 1
while a > div:
if a % div == 0:
a_div.append(div)
div += 1
div = 1
while b > div:
if b % div == 0:
b_div.append(div)
div += 1
c, d = 0, 0
gcd_list = []
for c in a_div:
for d in b_div:
if c == d:
gcd_list.append(c)
return max(gcd_list)
gcd = gcd(28, 42)
print("最大公約数は", gcd)
# 出力結果
# 最大公約数は 14
ユークリッドの互除法を使用する
ユークリッドの互除法の手順は次の通りです。
ステップ1. 2つの整数をa、bとする。
ステップ2. aをbで割った余りを求める。
ステップ3. bをステップ2で求めた余りで割り、その余りを求める。
ステップ4. 以下同様に繰り返すと余りが必ず0となる。余りが0になったときの割る数が最大公約数になる。
gcd2.py
def gcd(a, b):
while b: # bが0(False)になると終了
a, b = b, a % b
return a # 終了したとき最大公約数はa
gcd = gcd(28, 42)
print("最大公約数は", gcd)
# 出力結果
# 最大公約数は 14
再帰的なユークリッドの互除法を使用する
再帰とは、ある関数が自分自身を呼び出すプロセスのことですね。
こんな感じです。
gcd3.py
def gcd(a, b):
if b == 0: # 無限ループにならないための終了条件
return a
r = a % b
d = gcd(b, r) # ここで再帰を使用
return d
gcd = gcd(28, 42)
print("最大公約数は", gcd)
# 出力結果
# 最大公約数は 14
三項演算子を使って簡潔に書く
変数 = (条件が真のときに返す値) if (条件) else (条件が偽のときに返す値)というように三項演算子を使用しています。
gcd4.py
def gcd(a, b):
return gcd(b, a % b) if b else a
gcd = gcd(28, 42)
print("最大公約数は", gcd)
Pythonの標準関数を使用する
Pythonには、mathモジュールにgcd()という最大公約数を求める便利な標準関数があるので、それを使うのが一番簡単です。
gcd5.py
import math
gcd = math.gcd(28, 42)
print("最大公約数は", gcd)
# 出力結果
# 最大公約数は 14
私が最初に書いたコード
「最大公約数を求めよ」という課題に対して私が最初に書いたコードがこちらです。
いちおうユークリッドの互除法を使っていますが冗長な部分がありますね。でも懐かしいです。
gcd_saisho.py
def gcd(a, b):
while a != 0 and b != 0:
if a > b:
c = a % b
a = c
else:
c = b % a
b = c
if a == 0 or b == 0:
if a != 0:
return a
else:
return b
gcd = gcd(28, 42)
print("最大公約数は", gcd)
# 出力結果
# 最大公約数は 14
最小公倍数も求めてみる
正の整数a, bに対して、それらの最大公約数をgcd、最小公倍数をlcmとおくと、gcd(a, b) * lcm(a, b) = a * b
の関係が成り立つことを利用します。
最大公約数を求める関数も違う書き方で定義してみます。
gcd_lcm.py
def gcd(a, b):
x = max(a, b)
y = min(a, b)
if x % y == 0:
return y
else:
while x % y != 0:
z = x % y
x = y
y = z
else:
return z
def lcm(a, b):
return int(a * b / gcd(a, b))
print(gcd(24, 18)) # 出力結果は6
print(int(lcm(24, 18))) # 出力結果は72