ユークリッド互除法とは？
ゆーくりっどごじょほう
ユークリッド互除法とは、2つの正の整数 a と b（a > b）の最大公約数を、a を b で割った余りを用いて繰り返し計算することで求めるアルゴリズムである。「gcd(a, b) = gcd(b, a mod b)」という関係を余りが0になるまで再帰的に適用する。古代ギリシャの数学者ユークリッドが著書『原論』に記した、現存する最古のアルゴリズムの一つである。
使い方・例文
48と18の最大公約数を求めるとき、ユークリッド互除法では48÷18の余り12、18÷12の余り6、12÷6の余り0と進め、答えは6と求まる。
この用語をシェア
最終更新: