ユークリッドの互除法を用いて最大公約数を高速に算出する
整数a, bの最大公約数を求める。
2つ整数a, bの最大公約数はユークリッドの互除法を用いる事で高速に算出することができる。
ユークリッドの互除法とは
2つの自然数a, b(a >= b)の最大公約数は、a, bの余りをrとした時にbとrの最大公約数と等しい。
というものだ。
ソースコード
計算量
ラメの定理より、計算量はaとbの小さい方の桁数の5倍らしい。 つまり、109の整数同士の最大公約数を算出するための計算量はO(45)になるらしい。