前言

在做C语言相关练习的时候，会遇见比较经典的一道题型，就是求最大公约数或者最小公倍数。今天简单介绍几种方法来求解此种题目

一、大致思路

1.暴力求解

以求最大公约数为例，若求 a b 的最大公约数，所求的数最大不会超过两个数中较小的数。那可以从这个较小的数开始被a b同时试除，如果试除的余数为0，那么该数即为所求。如果不满足余数同时为零的条件，那么该数减一，接着试除，直到满足余数同时为零的条件为止。

基于以上思路可以写出如下代码

#include<stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	int max = (a > b ? b : a);//最大公约数从较小的数开始试除
	for (int i = max; i>0; i--)
	{
		if (a % i == 0 &&b % i == 0)
		{
			printf("%d",i );
			break;
		}

	}

	return 0;
}

如果是想求最小公倍数，基于上述思路从两数中最大的数开始试除即可。不过此时i是被除数。



不过基于试除法，对于最小公倍数的求解还有一种优化方法。若a b中最大的数是a，每次a从1倍开始增加，和b试除，直到余数为零。由此可以写出如下代码

#include<stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	int min = (a > b ? a : b);//最小公倍数从较大的数开始试除
	for (int i = 1;; i++)
	{
		if (i*a % b == 0)
		{
			printf("%d",a*i );
			break;
		}
	}
   return 0;
}

2.辗转相除法

辗转相除法是用来求最大公约数的，同时最小公倍数满足这样一条数学性质：两数之积除以最大公约数即为最小公倍数.所以用辗转相除法是可以间接求最小公倍数的。

辗转相除法的大概思路：用两数相除，如果余数为零即为所求，如果余数不为零，上一轮相除所得的余数为除数，同时上一轮的除数现在成为被除数，直到余数为零不再相除，此时的除数即为所求

#include<stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	int t = 0;//记录余数
	scanf("%d %d", &a, &b);
	while ( t = a % b )
	{
		a = b;
		b = t;
	}
	printf("%d", b);
   return 0;
}

同时求出了最大公约数，那么最小公倍数就很好求了

二、总结

1.注意事项

在使用试除法的时候注意i在算式中的位置，是除数还是被除数。

在使用辗转相除法求最小公倍数时记得保存 a b的初始值

同时若是不理解辗转相除法可以试着画图举例来加深印象理解其流程

2.结束语

本人能力有限，关于最大公约数和最小公倍数的求解这里只是简单的介绍几种，如有错误，欢迎指出!