こんにちは。
野中やすおです。
今回の記事では、Pythonを使って2つの自然数の最大公約数を求める方法を紹介します。
この方法は、ユークリッドの互除法と呼ばれます。
ユークリッドの互除法とは？
ユークリッドの互除法とは、
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と bとの最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
by Wikipedia
Pythonによるユークリッドの互除法の表現
以下のコードは全て、Python3による書き方です。
|
1 2 3 4 5 6 |
def gcd(x, y): if y == 0: return x else: return gcd(y, x % y) #再帰定義 print(gcd(10, 20)) #出力値：10 |
上記のコードでは、求めたい２つの自然数であるx = 10, y = 20の最大公約数である10が出力されます。
再帰定義とは、関数の定義の中に自分自身を呼び出すことを言います。
標準入力を使った書き方
また例として入力値がそれぞれ10, 20の場合には、標準入力を使った書き方が以下のようになります。
|
1 2 3 4 5 6 7 |
x, y = map(int, input().split()) #map関数を使って入力値を取得する def gcd(x, y): if y == 0: return x else: return gcd(y, x % y) print(gcd(x, y)) #出力値：10 |
以上、Pythonで2つの自然数の最大公約数を求めてみました。
