21:09:21)追加された行はこの色です。削除された行はこの色です。2つの整数の最大公約数(GCM)を求めるもっとも素朴な方法は、2,3,5,...とmin(a,b)以内の素数について割っていくことである。割った結果、2つの整数が割り切れれば、その公約数にはその素数が含まれるということを意味する。最大公約数はこうした素数のすべての掛け合わせたものである。このアルゴリズムは次の通りである。ところが、このアルゴリズムでは、min(a,b)以下のすべての素数のリストを用意しておかなければならない。これを解決するアルゴリズムのひとつがユークリッドの互除法である。ユークリッドの互除法では、素数を用意せずとも、どんな数の最大公約数でも求めることができる。2,000年以上前に[[ユークリッド]]によって発見されたアルゴリズムである。基本的なアルゴリズムともいえる。ユークリッドの互除法のアルゴリズムは次の通りである。2行目}}例:a=21,b=14の最大公約数(a,b)をユークリッドの互除法を使って求める。黄色の部分が初期値の入力である。出力結果は、水色のように0となった個所のひとつ上である。よって、赤色が最大公約数であり、これが出力される。このように素因数分解をせずに単に割り算をするだけで、最大公約数が求められるわけである。e){System.out.println("整数を入力してください。b==0){break;}//aとbを保存しておく。sa=a,sb=b;//割り切れるまで繰り返す。a;//最大公約数を表示する。");//最小公約数を表示する。大整数におけるユークリッドの互除法のプログラム(bigeuclid.java)を次に示す。a,b,r,a1,b1;System.out.println("正の整数a,bを入力せよ。ユークリッドの互除法を求めるときの表に着眼する。qSUB{n};の列がすべて1になるとき、即ち「∀n;qSUB{n};=1」のとき、繰り返し回数が一番多い。そのときの式は次のようになる。これはちょうどフィボナッチ数を定義する漸化式を逆順にしたものになっている。よって、互除法における繰り返し回数(lとする)の上限は次の不等式によって表される。\sqrt{5}}{2}");とする(このθは[[黄金比]]である((1:θ=θ:1-θを満たす)))。よって、繰り返し回数lはbの桁数程度ということを意味する。Javaではじめるアルゴリズム。