Pythonで最大公約数・最小公倍数を完全マスター【gcd・lcm算出・取得ガイド】
Pythonのmathモジュールを使えば、最大公約数（GCD）と最小公倍数（LCM）の計算を簡単に行うことができます。この記事では、基本的な計算方法から複数の数への拡張、実践的な応用まで詳しく解説します。
最大公約数（GCD）の基本
math.gcd()の使用
import math
# 2つの数の最大公約数
a, b = 48, 18
gcd_result = math.gcd(a, b)
print(f"gcd({a}, {b}) = {gcd_result}") # 6
# 様々なペアでのGCD
pairs = [(12, 8), (15, 25), (17, 19), (100, 75)]
print("a | b | gcd(a,b)")
print("-" * 20)
for a, b in pairs:
gcd_val = math.gcd(a, b)
print(f"{a:2} | {b:2} | {gcd_val:4}")
複数の数のGCD
import math
from functools import reduce
def gcd_multiple(*numbers):
"""複数の数の最大公約数を計算"""
return reduce(math.gcd, numbers)
# 3つ以上の数のGCD
numbers = [48, 18, 24, 36]
result = gcd_multiple(*numbers)
print(f"gcd{tuple(numbers)} = {result}") # 6
# リストからのGCD計算
number_list = [60, 48, 36, 24]
gcd_all = reduce(math.gcd, number_list)
print(f"gcd{number_list} = {gcd_all}") # 12
最小公倍数（LCM）の計算
GCDを使ったLCM計算
import math
def lcm_two_numbers(a, b):
"""2つの数の最小公倍数: lcm(a,b) = |a*b| / gcd(a,b)"""
return abs(a * b) // math.gcd(a, b)
# 2つの数のLCM
a, b = 12, 18
lcm_result = lcm_two_numbers(a, b)
print(f"lcm({a}, {b}) = {lcm_result}") # 36
# LCMの検証
gcd_val = math.gcd(a, b)
print(f"検証: {a} * {b} / gcd({a},{b}) = {a * b // gcd_val}")
複数の数のLCM
import math
from functools import reduce
def lcm_multiple(*numbers):
"""複数の数の最小公倍数を計算"""
def lcm_two(a, b):
return abs(a * b) // math.gcd(a, b)
return reduce(lcm_two, numbers)
# 複数の数のLCM
numbers = [4, 6, 8, 12]
result = lcm_multiple(*numbers)
print(f"lcm{tuple(numbers)} = {result}") # 24
# ステップごとの計算確認
print(f"lcm(4, 6) = {lcm_multiple(4, 6)}") # 12
print(f"lcm(12, 8) = {lcm_multiple(12, 8)}") # 24
print(f"lcm(24, 12) = {lcm_multiple(24, 12)}") # 24
Python 3.9以降のmath.lcm()
# Python 3.9以降では標準でlcm関数が利用可能
import sys
print(f"Pythonバージョン: {sys.version}")
try:
import math
# Python 3.9+の場合
if hasattr(math, 'lcm'):
result = math.lcm(12, 18, 24)
print(f"math.lcm(12, 18, 24) = {result}")
else:
print("math.lcm()は利用できません（Python 3.9未満）")
except Exception as e:
print(f"エラー: {e}")
ユークリッドの互除法の実装
基本的な実装
def gcd_euclidean(a, b):
"""ユークリッドの互除法によるGCD計算"""
while b:
a, b = b, a % b
return a
def gcd_recursive(a, b):
"""再帰版ユークリッドの互除法"""
if b == 0:
return a
return gcd_recursive(b, a % b)
# テスト
a, b = 48, 18
euclidean_result = gcd_euclidean(a, b)
recursive_result = gcd_recursive(a, b)
builtin_result = math.gcd(a, b)
print(f"ユークリッド法: gcd({a}, {b}) = {euclidean_result}")
print(f"再帰版: gcd({a}, {b}) = {recursive_result}")
print(f"標準関数: gcd({a}, {b}) = {builtin_result}")
拡張ユークリッドの互除法
def extended_gcd(a, b):
"""
拡張ユークリッドの互除法
ax + by = gcd(a, b) となる x, y を求める
"""
if b == 0:
return a, 1, 0
gcd, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return gcd, x, y
# 使用例
a, b = 35, 15
gcd_val, x, y = extended_gcd(a, b)
print(f"gcd({a}, {b}) = {gcd_val}")
print(f"{a} * {x} + {b} * {y} = {a*x + b*y}")
print(f"検証: {a*x + b*y} == {gcd_val}: {a*x + b*y == gcd_val}")
実践的な応用例
分数の約分
import math
class Fraction:
def __init__(self, numerator, denominator):
if denominator == 0:
raise ValueError("分母は0にできません")
# 約分処理
gcd_val = math.gcd(abs(numerator), abs(denominator))
self.numerator = numerator // gcd_val
self.denominator = denominator // gcd_val
# 分母を正にする
if self.denominator < 0:
self.numerator = -self.numerator
self.denominator = -self.denominator
def __str__(self):
if self.denominator == 1:
return str(self.numerator)
return f"{self.numerator}/{self.denominator}"
def __add__(self, other):
# 通分して加算
lcm_denom = abs(self.denominator * other.denominator) // math.gcd(self.denominator, other.denominator)
new_num = (self.numerator * lcm_denom // self.denominator +
other.numerator * lcm_denom // other.denominator)
return Fraction(new_num, lcm_denom)
# 使用例
frac1 = Fraction(12, 18) # 自動約分して 2/3
frac2 = Fraction(15, 25) # 自動約分して 3/5
print(f"12/18 → {frac1}")
print(f"15/25 → {frac2}")
print(f"{frac1} + {frac2} = {frac1 + frac2}")
周期的パターンの検出
import math
def find_pattern_period(sequence):
"""
数列の周期を見つける（GCDを利用）
"""
n = len(sequence)
possible_periods = []
for period in range(1, n // 2 + 1):
is_periodic = True
for i in range(period, n):
if sequence[i] != sequence[i % period]:
is_periodic = False
break
if is_periodic:
possible_periods.append(period)
return min(possible_periods) if possible_periods else n
# 使用例
periodic_sequence = [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
period = find_pattern_period(periodic_sequence)
print(f"数列の周期: {period}")
# フィボナッチ数列 mod 10の周期
fib_mod10 = []
a, b = 0, 1
for _ in range(60):
fib_mod10.append(a % 10)
a, b = b, (a + b) % 10
fib_period = find_pattern_period(fib_mod10)
print(f"フィボナッチ数列 mod 10の周期: {fib_period}")
歯車の設計
import math
def gear_ratio_calculation(teeth1, teeth2):
"""
歯車の歯数から最適な比を計算
"""
gcd_teeth = math.gcd(teeth1, teeth2)
simplified_ratio = (teeth1 // gcd_teeth, teeth2 // gcd_teeth)
# 1回転あたりの回転数
rotations_gear1 = teeth2 / teeth1
rotations_gear2 = teeth1 / teeth2
return {
'original_teeth': (teeth1, teeth2),
'simplified_ratio': simplified_ratio,
'gear1_rotations': rotations_gear1,
'gear2_rotations': rotations_gear2,
'common_factor': gcd_teeth
}
# 使用例
gear1_teeth = 24
gear2_teeth = 36
result = gear_ratio_calculation(gear1_teeth, gear2_teeth)
print(f"歯車1: {result['original_teeth'][0]}枚")
print(f"歯車2: {result['original_teeth'][1]}枚")
print(f"簡約比: {result['simplified_ratio'][0]}:{result['simplified_ratio'][1]}")
print(f"歯車1が1回転すると歯車2は{result['gear1_rotations']:.3f}回転")
暗号理論での応用
import math
def mod_inverse(a, m):
"""
拡張ユークリッドの互除法を使った逆元計算
ax ≡ 1 (mod m) となる x を求める
"""
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
gcd, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return gcd, x, y
gcd, x, _ = extended_gcd(a % m, m)
if gcd != 1:
raise ValueError(f"{a}と{m}は互いに素でないため、逆元が存在しません")
return (x % m + m) % m
# RSA暗号の簡単な例
def simple_rsa_example():
# 小さな素数を使用（実際には大きな素数を使用）
p, q = 7, 11
n = p * q # 77
phi_n = (p - 1) * (q - 1) # 60
# 公開鍵 e を選択（phi_nと互いに素）
e = 13 # gcd(13, 60) = 1
# 秘密鍵 d を計算（e * d ≡ 1 (mod phi_n)）
d = mod_inverse(e, phi_n)
print(f"p = {p}, q = {q}")
print(f"n = p * q = {n}")
print(f"φ(n) = (p-1)(q-1) = {phi_n}")
print(f"公開鍵: (e, n) = ({e}, {n})")
print(f"秘密鍵: (d, n) = ({d}, {n})")
# 暗号化・復号のテスト
message = 5
encrypted = pow(message, e, n)
decrypted = pow(encrypted, d, n)
print(f"\n平文: {message}")
print(f"暗号文: {encrypted}")
print(f"復号文: {decrypted}")
simple_rsa_example()
性能比較とベンチマーク
アルゴリズムの性能比較
import time
import math
def benchmark_gcd_algorithms():
# 大きな数での性能テスト
large_a = 123456789 * 987654321
large_b = 987654321 * 123456789
# 標準ライブラリ
start = time.time()
for _ in range(1000):
result1 = math.gcd(large_a, large_b)
time1 = time.time() - start
# ユークリッド法（自作）
start = time.time()
for _ in range(1000):
result2 = gcd_euclidean(large_a, large_b)
time2 = time.time() - start
print(f"大きな数でのGCD計算（1000回）:")
print(f"math.gcd(): {time1:.4f}秒, 結果: {result1}")
print(f"自作関数: {time2:.4f}秒, 結果: {result2}")
print(f"速度比: {time2/time1:.2f}倍")
benchmark_gcd_algorithms()
メモリ効率の考慮
import sys
def memory_efficient_gcd_list(numbers):
"""
大きなリストのGCDをメモリ効率よく計算
"""
if not numbers:
return 0
result = numbers[0]
for num in numbers[1:]:
result = math.gcd(result, num)
if result == 1: # これ以上計算不要
break
return result
# 大きなリストでのテスト
large_list = [2**i * 3**j * 5**k for i in range(5)
for j in range(3) for k in range(2)]
gcd_result = memory_efficient_gcd_list(large_list)
print(f"大きなリストのGCD: {gcd_result}")
print(f"リストサイズ: {len(large_list)}要素")
print(f"メモリ使用量: {sys.getsizeof(large_list)}bytes")
エラーハンドリングと注意点
負の数の処理
import math
def robust_gcd(a, b):
"""
負の数も含むGCD計算
"""
return math.gcd(abs(a), abs(b))
def robust_lcm(a, b):
"""
負の数も含むLCM計算
"""
if a == 0 or b == 0:
return 0
return abs(a * b) // robust_gcd(a, b)
# テスト
test_pairs = [(12, 18), (-12, 18), (12, -18), (-12, -18), (0, 5)]
print("a | b | GCD | LCM")
print("-" * 25)
for a, b in test_pairs:
try:
gcd_val = robust_gcd(a, b)
lcm_val = robust_lcm(a, b)
print(f"{a:4} | {b:4} | {gcd_val:4} | {lcm_val:4}")
except Exception as e:
print(f"{a:4} | {b:4} | エラー: {e}")
ゼロの扱い
import math
def gcd_with_zero_handling(a, b):
"""
ゼロを含む場合のGCD計算
gcd(a, 0) = |a|
gcd(0, 0) = 0（定義による）
"""
if a == 0 and b == 0:
return 0
elif a == 0:
return abs(b)
elif b == 0:
return abs(a)
else:
return math.gcd(abs(a), abs(b))
# ゼロを含む場合のテスト
zero_cases = [(0, 0), (0, 12), (15, 0), (7, 11)]
for a, b in zero_cases:
result = gcd_with_zero_handling(a, b)
builtin = math.gcd(a, b) if not (a == 0 and b == 0) else 0
print(f"gcd({a}, {b}) = {result} (標準: {builtin})")
まとめ
Pythonの最大公約数・最小公倍数計算は以下の特徴を持ちます：
math.gcd()による高速な計算- Python 3.9以降では
math.lcm()も利用可能 - 複数の数への拡張が容易
- 数論、暗号理論、工学計算での幅広い応用
GCDとLCMは、分数の約分、周期性の分析、歯車設計、暗号理論など、様々な実用的場面で重要な役割を果たします。適切なエラーハンドリングと効率的な実装を心がけながら、これらの基本的な数学関数を活用しましょう。
■プロンプトだけでオリジナルアプリを開発・公開してみた！！
■AI時代の第一歩！「AI駆動開発コース」はじめました！
テックジム東京本校で先行開始。
■テックジム東京本校
「武田塾」のプログラミング版といえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
より早く、より安く、しかも対面型のプログラミングスクールです。
＜短期講習＞5日で5万円の「Pythonミニキャンプ」開催中。
＜月1開催＞放送作家による映像ディレクター養成講座
＜オンライン無料＞ゼロから始めるPython爆速講座
