|
設(shè)兩個數(shù)分別為x，y(設(shè)x>y,如果x<y則交換x,y)
f(x,y) (設(shè)x>y,如果x<y則交換x,y)
x=p*z,p為素數(shù)，并且y%p！=0，（y不能被p整除），那么f(x,y)=f(p*z,y)=(z,y).
若x,y均為偶數(shù)，f(x,y)=2*f(x/2,y/2);
若x為偶數(shù)，y為奇數(shù)，f(x,y)=f(x/2,y);
若y為偶數(shù)，x為奇數(shù)，f(x,y)=f(x,y/2);
若y為奇數(shù)，x為奇數(shù)，f(x,y)=f(x,x-y);
int gcd(int x,int y){
if(x<y)
return gcd(y,x);
if(y==0)
return x;
else{
if(isEven(x)){
if(isEven(y))
return 2*gcd(x>>1,y>>1)
else
return gcd(x>>1,y);
}
else
{
if(isEven(y))
return gcd(x,y>>1)
else
return gcd(y,sxy); }
}
}其中isEven(int )為判斷是否偶數(shù)。 |
|
|
