最大公約数

読み:さいだい・こうやくすう
外語:G.C.D.: the greatest common divisor 米国英語 , G.C.M.: the greatest common measure 英国英語
品詞:名詞

二つ(以上)の整数公約数のうちで最大のもの。

目次

例えば、2と10の最大公約数は2である。

その計算方法は色々ある。最も単純な方法は、二つの整数AとBのそれぞれを素因数分解し、その共通項を見つける方法である。

例えば15と27の最大公約数は、15=3×5、27=3×9、であるので、答えは3である。しかしながら数が小さいうちは良いが、数が大きくなった場合は素因数分解は極めて難しくなるため、この方法は使えなくなる。

効率的な方法として古くから使われているものにユークリッドの互除法がある。

コンピューターで最大公約数を算出する場合も、この方法が最も一般的と考えられる。

用語の所属
公約数
約数
関連する用語
ユークリッドの互除法
最小公倍数
素因数分解

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club