有时,爱情能穿越宏大的沧桑抵达幸福,却穿越不了宁静的琐细。

最大公约数与最小公倍数

技术文档 12403浏览 0评论

最大公约数:
一、求两个数的最大公约数
求最大公约数主要有两种方法方法,辗转相除法(欧几里德算法)和移位相减法(Euclid & stein 算法)。
1、辗转相除法相对简单,相应的C代码如下:
int gcd(int a,int b)
{
 int t = 0;
 int c = 0;

if(a==0)return b;
if(b==0)return a;
if(a < b) {t=a;  a=b;  b=t; }
   c=a%b;
while(c!=0)
{a=b;b=c;c=a%b;}
return b;   
}

或者用递归函数:
int gcd_fun(int a,int b)
{
 int t;
 if(a<0||b<0) return -1;

 if(a==0)return b;
    if(b==0)return a;
 if(a < b)  { t=a;a=b;b=t;}
 if(a%b==0) return b; 
  return gcd_fun(b,a%b);
}

2、对于移位相减法,给出Stein算法如下:
1).如果A=0,B是最大公约数,算法结束
2).如果B=0,A是最大公约数,算法结束
3).设置A1 = A、B1=B和C1 = 1
4).如果An和Bn都是偶数,则An+1 =An /2,Bn+1 =Bn /2,Cn+1 =Cn *2(注意,乘2只要把整数左移一位即可,除2只要把整数右移一位即可)
5).如果An是偶数,Bn不是偶数,则An+1 =An /2,Bn+1 =Bn ,Cn+1 =Cn (很显然啦,2不是奇数的约数)
6).如果Bn是偶数,An不是偶数,则Bn+1 =Bn /2,An+1 =An ,Cn+1 =Cn (很显然啦,2不是奇数的约数)
7).如果An和Bn都不是偶数,则An+1 =|An -Bn|,Bn+1 =min(An,Bn),Cn+1 =Cn
8).n++,转4)
unsigned binary_gcd(unsigned x, unsigned y)
{
 unsigned temp;
 unsigned common_power_of_two = 0;
 if(x==0) return y ; //
 if(y==0) return x;
 while(((x|y)&1)==0){
  x=x>>1;
  y=y>>1;
  ++common_power_of_two;
 }
 while((x&1) == 0) x>>=1;
 while(y){
  while((y&1)==0) y =y>>1;
  temp = y;
  if(x>y) y = x - y;
  else y=y-x;
  x = temp;
 }
 return (x << common_power_of_two);
}

或者用递归
int gcd2(int a,int b)
{
    int t = 0;
    if(a < b)
 {t=a;a=b;b=t;}
    if(a==0)return b;
    if(b==0)return a;
    while(a != b)
    {      
        if(( (a&1) == 0 ) && ( (b&1) == 0 )){
            return 2*gcd2(a/2,b/2); //a,b are even numbers
        }else if(( (a&1) == 1 ) && ( (b&1) == 0)){
            return gcd2(a,b/2); //a is odd number , b is even number
        }else if(((a&1) == 0 ) && ( (b&1) == 1) ){
            return gcd2(a/2,b);//a....even   ;b ...odd ...
        }else if(((a&1) == 1 ) && ((b&1) == 1)){
            return gcd2(b,(a-b)); //a,b are odd numbers
        }  
    }
    return b;
}

二、求一组数的最大公约数
先求前两个数的最大公约数e1,再求e1与第三个数的最大公约数。......依此类推,可求出多个数的最大公约数。//通过递归调用求n个数的最大公约数
int ngcd(int a[],int n)
{
 if (n==1)  return a[0];
 else return gcd2(a[n-1],ngcd(a,n-1));
}

最小公倍数
一、求两个数的最小公被数
设两个整数为u和v,用辗转相除法求最大公约数的算法。最小公倍数=uv/最大公约数。所以其算法如下:
已知m,n均为正整数:
(1) 计算m*n的积,送临时变量r。
(2) 若m等于n,则输出最小公倍数r/m,算法结束。
(3) 若m大于n,计算m-n,结果送m,否则,计算n-m,结果送n。
(4) 转到(2)或者(3)。
int Min(int m,int n)
{
 int r;
 int result = 0;
 r=m*n;
 while(1)
 {
  if(m==n){ result= r/m; break;}
  if(m-n>0)
   m=m-n;
  else
   n=n-m;
 }
 return result;
}

二、求一组数的最小公倍数

注:
求最大公约数时,可以选择较小的数,然后将这个较小的树作为除数,分别除这两个数,如果能除尽,则这个小的数就是最大公约数,否则减一再除,知道较小的这个数减到1为止。
求最小公倍数时,可以选择较大的数,然后分别乘以1,2,3......一直到较小的数为止,如果乘积能被较小的数整除,则这个乘积就是最小公倍数。

转载请注明:自由的风 » 最大公约数与最小公倍数

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址