ユークリッドの互除法

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

整数a, bの最大公約数を求める。 2つ整数a, bの最大公約数はユークリッドの互除法を用いる事で高速に算出することができる。 ユークリッドの互除法とは ユークリッドの互除法とは 2つの自然数a, b(a >= b)の最大公約数は、a, bの余りをrとした時にbとrの最…