gcdアルゴリズム(最大公約数を求める)
gcdアルゴリズム:正の整数m,n(m>=n)を与え、それらの最大公約数を求めます.(一般的にはm>=nが要求されますが、m＜nの場合はm<->nを交換します.以下、具体的に説明します.)以下、このアルゴリズムの具体的な流れです. 1、[剰余を求める]は、r=m%nとし、rはmを除いた所得の剰余(0<=rr=m%n=119%68=51; m<-68,n<-51,=>r=m%n=68%51=17をセットします. m<-51,n<-17,=>r=m%n=51%17=0を放置して、アルゴリズムは終了します. このときのn=17はm=544,n=119で求められた2つの数の最大公約数である. 上記gcd(m,n)アルゴリズムの先頭におけるm>=nが要求されている理由を説明します.m＜n、m=119、n=544のような例を挙げると、r=m%n=119%544=119、 rですから0ですので、上記ステップ3を実行します.m<-544,n<-119です.見ましたか?最初にあげたm＜nですが、gcdアルゴリズムを実行するとm、nの値を交換して、m＞＝nを保証します.
/**
*
*
* @param m
* @param n
* @return
*/
public static int gcd(int m, int n)
{
if (m < 0 || n < 0)
{
System.err.println("ERROR!!");
return -1;
}
while (true)
{
if ((m = m % n) == 0)
return n;
if ((n = n % m) == 0)
return m;
}
}