【Python】ユークリッドの互除法で最大公約数を求める【アルゴリズム】

この記事は約2分で読めます。

ユークリッドの互除法について

概要

  • 最大公約数を求めるアルゴリズム
  • greatest common divisorの頭文字をとってgcdと表記されることがある

コード

[1]yが0の時

yが0の時、xを返します。すでに最大公約数が求まっている状態です。

[2]yが0以外の時

xの値をyとし、yの値をxをyで割ったときの余りとして再度この関数を呼び出します。

xでyが割り切れる、つまり[1]のようにyが0になるまで再帰的に処理を繰り返します。

 

また、Pythonではmathモジュールを使うことで簡単に最大公約数を求めることもできます。

 

 

 

参考

こちらの書籍を用いて学習しています。

問題が書籍の中にあります。図を使って各頂点と各辺のコストが示されているので、書籍を手元に準備すると理解しやすくなると思います。

また、こちらのサイトも学習に利用しています。

Pythonで最大公約数と最小公倍数を算出・取得 | note.nkmk.me

 

Atcoderに最大公約数を求める問題があります。

022 – Cubic Cake(★2) (atcoder.jp)

こちらの記事で上記の問題を解いてみました。

【Atcoder】競プロ典型問題90問に挑戦 | Best Practice (find-best-practice.com)

コメント