用C语言解决最大公约数问题

用户10922923

发布于 2024-01-23 09:34:39

1670

发布于 2024-01-23 09:34:39

文章被收录于专栏：兵马俑的CSDN兵马俑的CSDN

1.题目描述：

输入2个整数m和n,计算m和n的最大公约数，并打印出结果。

2.解法思路：

首先我们要考虑，什么是最大公约数，在数学中的定义是：最小公倍数是指两个或多个整数共有倍数中最小的一个。为了求出两个数的最下公倍数，可以采用枚举试错法。

注：枚举试错法（也被称为暴力搜索）是从一组可能的解决方案中寻找符合条件的解决方案的一种计算机算法。它通常是通过测试所有可能的解决方案来实现的，直到找到符合条件的解决方案。

枚举试错法的基本思想是枚举所有可能的解决方案，然后对每个解决方案进行测试，检查其是否符合条件。如果找到符合条件的解决方案，则算法停止并返回该解决方案。

由于枚举试错法测试所有可能的解决方案，因此它通常需要比其他更高级的算法更多的时间和计算资源。但是，它具有简单、直观、可靠和普适性的优点，因此在一些问题的求解中仍然被广泛使用。

1. 具体来说，公倍数?定大于两个数，从两个数中的较大值开始枚举；

2. 从小到大依次判断能否同时整除这两个数，若某个数满足同时被两个数整除，则其为公倍数；

3. 从小到大遍历找到公倍数时，此数即为最小公倍数，此时应当结束循环；

特别地：最小公倍数可以由两数乘积除以两数的最大公约数求得。

3.代码展示

#include<stdio.h>
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d %d", &m, &n);
	//计算m和n的较大值；m和n的最小公倍数，最小也是m和n中较大的值
	int k = (m > n ? m : n);
		while (1)
		{
			//若K被两数同时整除，则K为公倍数，并且此时一定是最小公倍数；
			if (k % m == 0 && k % n == 0)
			{
				printf("%d\n", k);
				break;
			}
			//k的值加一，对下一个数进行判断；
			k++;
		}
		return 0;
}