Find the maximum common divisor and least common multiple

题目

输入数字m和n，求m和n的最大公约数和最小公倍数

思路

首先输入m和n两个数

由于mn的最大公约数大于mn中最大的数，mn最小公倍数大于mn中最大的数

那么可以以mn中最大的数字(另外设为x)为基准，用x不断减小去找最大公约数，用x不断增大去找最小公倍数

另外值得注意到是最大公约数不为m或者n本身，所以初始设置要把x-1

寻找最大公约数

• 设a=x-1，a++
• 当m与n都整除a时停止
• 输出a

寻找最小公倍数

• 设b=x，b++
• 当b整除m又整除n时停止
• 输出b

代码

#include<stdio.h>

int main()
{
	int m = 0, n = 0, x = 0, a = 0, b = 0;

	printf("请输入m和n的值：\nm = ?");
	scanf("%d", &m);
	printf("n = ?");
	scanf("%d", &n);

	x = ((m >= n) ? m : n);

	for(a = x - 1; 1; a--)
	{
		if (0 == m % a && 0 == n % a)
		{
			printf("m和n的最大公约数为%d\n", a);
			break;
		}
	}

	for (b = x; 1; b++)
	{
		if (0 == b % m && 0 == b % n)
		{
			printf("m和n的最大公约数为%d\n", b);
			break;
		}
	}
	return 0;
}