【ユークリッドの互除法】最大公約数の計算

ユークリッドの互除法で最大公約数を求めるアルゴリズムをまとめました。

スポンサーリンク

ユークリッドの互除法

「ユークリッドの互除法」とはm2つの自然数 a,b の最大公約数を効率的に計算する方法で、世界最古のアルゴリズムとしても有名です。

ユークリッドの互除法では、「aをbで割ったときの余りrとすると、aとbの最大公約数とbとrの最大公約数が等しくなる」性質を用いています。

ユークリッド互除法で2つの自然数a, bの最大公約数を求める手順は以下の通りです。

処理手順
a ÷ b の余りrを計算する。
余りrをb、元のbをaとして手順①をr=0になるまで繰り返す。
r=0になったときのbが最大公約数となる。

※2つの自然数a, bのうち大きい方をa, 小さい方をbとする

スポンサーリンク

例題

ユークリッド互除法の計算例として、「54545454」と「121212」の最大公約数を求めてみます。

54545454 ÷ 121212 = 450 余り 54
121212 ÷ 54 = 2244 余り 36
54 ÷ 36 = 1 余り 18
36 ÷ 18 = 2 余り 0

余りr=0になったときのb(割られる数)は18なので、最大公約数は18となります。

関連ページ
1 【情報処理入門】基礎用語・原理・資格まとめ
IPA試験対策
スポンサーリンク

コメント