ユークリッドの互除法を用いて最大公約数を高速に算出する

整数a, bの最大公約数を求める。

２つ整数a, bの最大公約数はユークリッドの互除法を用いる事で高速に算出することができる。

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

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

２つの自然数a, b(a >= b)の最大公約数は、a, bの余りをrとした時にbとrの最大公約数と等しい。

というものだ。

ソースコード

計算量

ラメの定理より、計算量はaとbの小さい方の桁数の５倍らしい。 つまり、10⁹の整数同士の最大公約数を算出するための計算量はO(45)になるらしい。