辗转相除法---求最大公约数和最小公倍数

亦凉 2024-04-03 14:10 89阅读 0赞

> 1.正常想法

关于求解，正常的想法都是： 循环一个个数试验。但是， 这样数据小没问题，数据大的时候，将占用内存过大无法实现，导致没有输出值。

#include <stdio.h>
    //暴力求解：
    //耗时太久，不满足条件
    int main()
    {
    	long long n = 0;
    	long long m = 0;
    	long long tmp = 0;
    
    	scanf("%lld %lld", &n, &m);
    	long long max = m > n ? n : m;
    	while (max)
    	{
    		if (m % max == 0 && n % max == 0)
    		{
    			break;
    		}
    		max--;
    	}
    	long long min = m > n ? m : n;
    	while (min)
    	{
    		if (min % m == 0 && min % n == 0)
    		{
    			break;
    		}
    		min++;
    	}
    	printf("%lld\n", max + min);
    	return 0;
    }

正常输出值如下：

![2ee447bda1454cb1b0feaf96ad064137.png][]

数据过大时：

![d8dc3d1aaea549d98e0c45d1a03bdbf6.png][]

编译器一直在循环，结束时间无法预计。

所以这样我们就应该采用一个新的方法：辗转相除法。

> 辗转相除法--即连续取模方法。（最大公约数）

如：求 27与6的最大公约数？

27%6=3；将27的位置让给6；6的位置让给3；

即：6%3=0；此时即求出最大公约数。

用字母表示即为：

a%b=c；如果b%c=0；c即为最大公约数，否则继续执行。

> 最小公倍数

知道最大公约数，求解最小公倍数也是非常简单！

因为最小公倍数与最大公约数之积等于两数之积。

即max\*min=m\*n；

所以：min=m\*n/max；

#include <stdio.h>
    
    int main()
    {
    	long long n = 0;
    	long long m = 0;
    	scanf("%lld %lld", &n, &m);
    	long long tmp = 0;
    	long long min = 0;
    	long long max = 0;
    	long long a = n;
    	long long b = m;
    	while (tmp = a % b)
    	{
    		a = b;
    		b = tmp;
    	}
    	max = b;
    	min = n * m / max;
    	printf("%lld", min + max);
    	return 0;
    }

防止输入值过大，所以要把所有变量定义为long long。

> 总结：

第一次技术分享，如果有错误，希望大家指出，感谢大家收看！

[2ee447bda1454cb1b0feaf96ad064137.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3ef9fdcb2feb4904a1f15320f4e9dafd.png
[d8dc3d1aaea549d98e0c45d1a03bdbf6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b7e6d6f7aea54a55909936f44719fe05.png