最大公約数
読み：さいだい-こうやくすう
外語：G.C.D.: the greatest common divisor
二つ(以上)の整数の公約数のうちで最大のもの。
特徴
例えば、2と10の最大公約数は2である。
その計算方法は色々ある。最も単純な方法は、二つの整数AとBのそれぞれを素因数分解し、その共通項を見つける方法である。
例えば15と27の最大公約数は、15=3×5、27=3×9、であるので、答えは3である。しかしながら数が小さいうちは良いが、数が大きくなった場合は素因数分解は極めて難しくなるため、この方法は使えなくなる。
計算
効率的な方法として古くから使われているものにユークリッドの互除法がある。
コンピューターで最大公約数を算出する場合も、この方法が最も一般的と考えられる。
再検索