【Python】最大公約数と最小公倍数の求め方

この記事では、Python で最大公約数と最小公倍数を求める方法を解説します。

最大公約数

最大公約数とは、いくつかの正の整数に共通な約数(公約数)のうち最大のもの のことを言います。

最大公約数は、ユークリッドの互除法を使って以下のように求めることができます。

def gcd(a ,b):
  if b == 0: 
    return a 
  else:
    return gcd(b, a % b)

print(gcd(4, 12))
print(gcd(100, 250))
print(gcd(15, 835))

実行結果

4
50
5

Python 3.5 から mathモジュール に gcd()関数 が追加されました。

import math

math.gcd(*integers)

任意の数の整数の最大公約数を取得することができます。

import math

print(math.gcd(12, 1152, 336, 72))

実行結果

12

最小公倍数

最小公倍数とは、いくつかの正の整数に共通な倍数(公倍数)の中で最小のもの のことを言います。

最小公倍数は、以下の計算式で求めることができます。

math.gcd()関数 を使うことで簡単に実装できる。

import math

def lcm(a, b):
    return int(a * b / math.gcd(a, b))

print(lcm(4, 6))
print(lcm(2, 7))
print(lcm(3, 14))

実行結果

12
14
42

Python 3.9 から mathモジュール に lcm()関数 が追加されました。

import math

math.lcm(*integers)

任意の数の整数の最小公倍数を取得することができます。

import math

print(math.lcm(4, 6))
print(math.lcm(2, 7, 13))
print(math.lcm(3, 14, 10))

実行結果

12
182
210

まとめ

この記事では、Python で最大公約数と最小公倍数を取得する方法を解説しました。

Python 3.5 から最大公約数を計算できるgcd()関数、Python 3.9 から最小公倍数を計算できる lcm()関数 が追加されているのでバージョンに合わせて使っていきましょう！

それでは今回の内容はここまでです。ではまたどこかで〜( ・∀・)ﾉ