Pythonで2つの自然数の最大公約数を求めてみる(ユークリッドの互除法)。

こんにちは。とむるです。

今回の記事では、Pythonを使って2つの自然数の最大公約数を求める方法を紹介します。

この方法は、ユークリッドの互除法と呼ばれます。

ユークリッドの互除法とは?

ユークリッドの互除法とは、

2 つの自然数 ab (a ≧ b) について、a の b による剰余を r とすると、 a と bとの最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
by Wikipedia

またユークリッドの互除法】やり方&証明を解説!センター試験にも役立つ!というサイトが大変に参考になりました。大学入試にも使えるそうです(知らなかった・・・)。

Pythonによるユークリッドの互除法の表現

以下のコードは全て、Python3による書き方です。

上記のコードでは、求めたい2つの自然数であるx = 10, y = 20の最大公約数である10が出力されます。

再帰定義とは、関数の定義の中に自分自身を呼び出すことを言います。

標準入力を使った書き方

また例として入力値がそれぞれ10, 20の場合には、標準入力を使った書き方が以下のようになります。

以上、Pythonで2つの自然数の最大公約数を求めてみました。

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

ABOUTこの記事をかいた人

とむる

文系大学院を修了したITエンジニア。関心テーマは会計、ファイナンス、データ分析、経済学、旅行など。このブログでは、とむるの興味のあるテーマを扱っていく予定です。