最大公约数和最小公倍数

最大公约数函数命名一般是gcd

最小公倍数函数命名一般是lcm

一般来说，会先算最大公约数，因为有一种算法 是利用这个最大公约数来求最小公倍数，这种算法通常被称为“最大公约数与最小公倍数的关系算法”或者“基于最大公约数求最小公倍数的算法” ，但并没有一个特别固定且广泛认可的专用名称。

我们先抛开这些，先来看最小公倍数

1、最小公倍数

公倍数是什么？

如果正整数a的倍数有: c、d、e、f

如果正整数b的倍数有:d、f、g、h

d、f是a和b公有的倍数，叫做公倍数

其中除0以外的最小的公倍数，叫做最小公倍数。

例如:120和60都是12和15的公倍数，但60是12和15的最小公倍数。

最大公倍数不用算，就是两个数相乘吗？不，没有最大公倍数这一说，乘完我再乘任意数，不还是公倍数吗？

因此只有计算最小公倍数才是有意义的

如何计算？

scratch

套用一个scratch的流程图

思路：

得到2个数 a,b

将最小公倍数设定为其中一个a或b都可以，不影响，然后用这个数去模另一个数，如果可以整除，说明这个数就是最小公倍数

如果不可以整除第二个数，就把这个数加1，再去模第二个数

如果不可以整除，就把这个数继续加1，直到可以模第二个数为0，即整除，那么此时这个数是多少，就是最小公倍数

因为不知道要加几次1，因此要用一个无限循环配合break来进行计算

那么，C语言和python语言的代码也差不多就出来了

C语言方法1：

一般会先算最大公约数，然后可以利用这个最大公约数来求最小公倍数

也可以不用最大公约数，直接计算最小公倍数

我们先来看不利用最大公约数的算法，因为我们还没有做最小公倍数

	//计算最小公倍数lcm（不通过最大公约数）
	int a = 2;	//第1个数
	int b = 3;	//第2个数
	int i=1;	//乘以多少
	int lcm = a;//设其中一个为最小公倍数，当然此时它可能不是
	while(1)	//无限循环开始
	{
		if(lcm * i % b == 0)	//如果我们设定的最小公倍数乘以1，能整除第二个数
		{
			printf("%d",lcm* i);//说明此时它乘以1，也就是说自己就是最小公倍数
			break;				//跳出循环
		}	
		i++;					//如果乘以1不能整除第二个数，就乘以2，乘以3，直到满足上面的if
	}

C语言方法2：

	//计算最小公倍数lcm（不通过最大公约数）
	int a = 2;	//第1个数
	int b = 3;	//第2个数
	int max=a>b?a:b;	//找出其中大的数

	int lcm = max;//设大的一个为最小公倍数，当然此时它可能不是
	while(1)	//无限循环开始
	{
		if(lcm % a == 0 && lcm % b == 0)	//如果我们设定的最小公倍数乘以1，能整除第二个数
		{
			printf("%d",lcm);//说明此时它乘以1，也就是说自己就是最小公倍数
			break;				//跳出循环
		}	
		lcm++;					//如果乘以1不能整除第二个数，就乘以2，乘以3，直到满足上面的if
	}

python语言

a=2
b=6
lcm = a
i=1
while(1):
    if lcm*i % b == 0:
        print(lcm*i)
        break
    i+=1

根据上面的C语言，python也可以第2种方法，但是篇幅原因就不写了

以上就是不通过最大公约数来计算两个数的最小公倍数的方法，当然有一定局限性，比如，如果是多个数的最小公倍数怎么办？那一定是需要用到数组和函数的，这里先不说

2、最大公约数（公因数）

也叫最大公因数

所谓因数就是可以整除某个数的几个数

如果正整数m的因数有 : c、d、e、f

如果正整数n 的因数有 : d、f、g、h

d、f是a和b公有的因数，叫做公因数。

其中最大的公因数，叫做最大公因数。

7和13的最大公因数是1

2个质数的最大公因数是1

例如:

24的因数有:1、2、3、4、6、8、12、24

36的因数有:1、2、3、4、6、9、12、18、36

24和26的公因数有:1、2、3、4、6、12

24和36的最大公因数是:12

scratch

这里分两种方法：枚举法和辗转相除法

枚举法

最重要的第一步是，得到两个数中，较小的那个数

因为因数不可能大于自己，比如2，4两个数，因数不可能是4，不能比2大，所以最低要求是，较小的那个数

#include <stdio.h>
int main()
{
	int a=15;
	int b=30;
	int gcd = a<b?a:b;	//最大公约数应当是两数中小的那个，不可能是大的那个
	while(gcd>0)	//设定最大公约数为小的那个
	{
		if(a % gcd == 0 && b % gcd ==0)	//如果两个数模这个小点的数都可以整除
		{
			printf("%d",gcd);		//说明这个小点的数就是最大公约数
			break;
		}
		gcd--;			//否则，将这个小点的数减1，再让两个数都去模看能否整除
		//最终当减到1的时候，一定可以让两个数都模除结果为0
		//如果出现这种情况，1是最大公约数，那么说明这两个数都是质数
	}
}

上面这种方法，效率比较低，在对执行时间有要求的情况下，如果数字较大，每次减1再计算，明显会用更多时间，比如1000000和10000005，这样的话，得减很多次再去模，一般常用的是下面这个方法

辗转相除法(欧几里得算法)

这是最常见的方法。用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是 0 为止。最后的除数就是这两个数的最大公约数。

例如：求 252 和 105 的最大公约数

252 ÷ 105 = 2…42
105 ÷ 42 = 2…21
42 ÷ 21 = 2…0

所以 252 和 105 的最大公约数是 21。

代码如下：注意不要看混乱了

#include <stdio.h>
void main()
{
	int m,n,t;
	printf("请输入两个整数：");
	scanf("%d%d",&m,&n);
	t=m%n;
	/**********Program**********/
	while(t)
	{
		m=n;
		n=t;
		t=m%n;
	}
	/**********  End  **********/	
	printf("最大公约数是：%d\n",n);
}

更相减损术

用较大数减去较小数，然后将差和较小数比较，再用大的减去小的，如此反复，直到两个数相等为止，这个相等的数就是最大公约数。

例如：求 98 和 63 的最大公约数

98 - 63 = 35
63 - 35 = 28
35 - 28 = 7
28 - 7 = 21
21 - 7 = 14
14 - 7 = 7

所以 98 和 63 的最大公约数是 7

3、利用最大公约数来求最小公倍数

先求出最大公约数，然后有一个公式：lcm = a*b / gcd(a,b)

因此可以看出，要使用自定义函数

C语言代码：

#include <stdio.h>

// 计算最大公约数
int gcd(int a, int b) {
	int temp= a%b;
	while (temp) {
		a=b;
		b=temp;
		temp = a%b;
	}
	
//	while (b) {
//		temp = b;
//		b = a % b;
//		a = temp;
//	}
	
	return b;
}

// 通过最大公约数计算最小公倍数
int lcm(int a, int b) {
	return (a * b) / gcd(a, b);
    //# 注意这里a*b要包括号，运算符优先级要考虑好
}

int main() {
	int num1 = 6, num2 = 18;
	int gcd1 = gcd(num1,num2);
	int result = lcm(num1, num2);
	printf("最小公倍数为: %d\n", result);
	printf("最大公约数为: %d\n", gcd1);
	return 0;
}

用python就简洁多了：

#利用gcd求lcm
def gcd(a,b):   #最大公因数，a,b代表两个数，将b给a,将a%b的结果给b
    while b!=0: # 需要循环辗转相除
        a,b = b,a%b # 将b的值给a，将a%b的值给b，终有一次a%b会是0
    return b
def lcm(a,b):
    return (a*b) // gcd(a,b)
# 注意这里a*b要包括号，运算符优先级要考虑好
#//是整除，不要小数部分，在C语言里，因为有类型int，因此直接用/除，得到的就是整数部分
num1 = 12
num2 = 18
print(f'最小公倍数是：{lcm(num1,num2)}')