Euclid の互除法

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /euclidean-algorithm#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /euclidean-algorithm#noredirect を利用してください。
name
Euclid の互除法
short description
Euclid の互除法とは、ふたつの自然数の最大公約数を求めるアルゴリズムのひとつ。
input
自然数 $a, b$
output
最大公約数 $\mathrm{gcd}(a, b)$
time complexity
$O(\log a + \log b)$