求两个数的最大公约数和最小公倍数

时间:2021-07-29 12:37:20

最大公约数 解释

最小公倍数 解释

求两个数的最大公约数和最小公倍数,只要计算出最大公约数可以求得最小公倍数

两个数字a和b,假设最大公约数为m,a=a1*m,b=b1*m,最小公倍数是a1*b1*m=(a*b)/m

 

算法一 穷举法

按1、2、3...的顺序判断,能同时被两个数整除的最大的数是最大公约数

改进

假设a<b,按a、a-1、a-2...的顺序判断,第一个能同时被两个数整除的是最大公约数

int GetGCD(int x, int y)
{
	int i;
	for(i=x;;i--)
	{
		if(x%i==0&&y%i==0)
		break; 
	}
	return i;
}

  

 

算法二 辗转相除法(欧几里得算法)

第一步:令r为a/b所得余数(0≤r<b)
若 r= 0,算法结束;b 即为答案。
第二步:互换,置 a←b,b←r,并返回第一步。

int GetGCD(int m,int n)
{
  if(m == 0||n == 0)
	return 0;

  if(m < n)
	return GetGCD(n, m);
		
    if (m % n == 0)
        return n;
  else
        return GetGCD(n,m % n);
}

  

 

算法三 更相减损法

第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

int GetGCD(int a,int b)
{
    while(a!=b)
    {
        if(a>b)     
		a-=b;
	else  
		b-=a;
    }
    
    return a;
}

  

 

 

 

 

 以上代码只是提供思路并未进行验证。

来源:内部测试