JAva最大公約数gcd
2955 ワード
最大公因数は、最大公約数、最大公因数とも呼ばれ、2つ以上の整数共有約数のうち最大の1つを指す.a,bの最大公約数は(a,b)、同様に、a,b,cの最大公約数は(a,b,c)、複数の整数の最大公約数にも同様の記号がある.最大公約数を求めるには様々な方法があり、よく見られる有質因数分解法、短除法、転がり相除法、更相減損法である.最大公約数に対応する概念は最小公倍数であり、a,bの最小公倍数は[a,b]と記す.この実現方式は転がり相除法である:
ベースインプリメンテーションメソッド(再帰的インプリメンテーション)
公約数アルゴリズムをすばやく解く:
基本回転相殺アルゴリズム:
ベースインプリメンテーションメソッド(再帰的インプリメンテーション)
public int GCD(int a,int b) {
if(b==0)
return a;
else
return GCD(b,a%b);
}
公約数アルゴリズムをすばやく解く:
public int Quick_GCD(int a,int b)
{
if(a==0) return b;
if(b==0) return a;
if(!(a%2==1)&&!(b%2==1))
{
return Quick_GCD(a>>1,b>>1)<<1;
}
else if(!(b%2==1))
{
return Quick_GCD(a,b>>1);
}
else if(!(a%2==1))
{
return Quick_GCD(a>>1,b);
}
else
{
return Quick_GCD(Math.abs(a-b),Math.min(a,b));
}
}
基本回転相殺アルゴリズム:
public int GCD_base(int a,int b)
{
int r;
while(b>0)
{
r=a%b;
a=b;
b=r;
}
return a;
}