[Python] ユーグリッドの互除法で最大公約数を求める

アルゴリズムの勉強で、ユーグリッドの互除法が出て来たので実際にpythonで書いてみました。

ユーグリッドの互除法とは

2つの自然数の最大公約数を求める方法の一種。

世界最古のアルゴリズムと言われている。

通常、2つの数の最大公約数を求める場合には、以下のように求めるかと思います。

1112  = 139 * 2 * 2 * 2

695 = 139 * 5

=> 139が最大公約数

数字が小さい時は、問題ないのですが大きくなると計算量が半端なくなってしまいます。

そこで、ユーグリッドの互除法では、より効率よく最大公約数を求めることができます。

計算方法

modは、割り算した余りを求めます。

1112 mod 695 = 417

695 mod 417 = 278

417 mod 278 = 139

278 mod 139 = 0

=> 139が最大公約数

 

コード例

 

まとめ

数学を勉強したくなりました。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA