C语言求两数的最大公约数和最小公倍数

用vs2021编辑

1.程序目标

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

2.设计程序

1）运用更相减损法求最大公约数

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

2）再运用最  最大公约数*最小公倍数=两数相乘  来求最小公倍数

代码如下

#include
int a, b, x, y,c1,c2;
int main()
{
	printf("请输入两个数：");
	scanf_s("%d%d", &x, &y);
	c2 = divisor( x,  y);
	printf("最大公约数是 %dn", c2);
	c1 = x * y / c2;				//最大公约数*最小公倍数=两数相乘
	printf("最小公倍数为 %dn", c1);
	return 0;

}
int divisor(int x, int y)			//最大公约数，用更相减损术求公约值
{
	int t = 0;
	if (x > y)
	{
		a = x; b = y;
	}
	else
	{
		a = y; b = x;
	}
	if (x % 2 == 0 && y % 2 == 0)
	{
		x = x / 2; y = y / 2;
	}
	while (a != b)
	{
		a = a - b;
		if (a < b)
		{
			t = a;
			a = b;
			b = t;
		}
	}
	return a;
}