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

最大公约数 解释

最小公倍数 解释

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

两个数字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;
}

　　

 

 

 

 

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

来源：内部测试