ユークリッドの互除法
入力された2つの整数のうち小さいほうの整数 "n" の桁数を "d" とすれば、ユークリッドの互除法では O("d") 回の除算で最大公約数が求められる。桁数 "d" は O(log "n") なので、ユークリッドの互除法では O(log "n") 回の除算で最大公約数が求められる。