什么是公约数？/最大公约数求法（欧几里得算法/辗转相除法）

目录

什么是公约数？

辗转相除法（欧几里得算法）

代码实现

---

什么是公约数？

????????想要求得最大公约数首先要知道什么是公约数（又称公因数）是指能同时整除几个整数的数?。如果一个整数同时是几个整数的约数，称这个整数为它们的“公约数”；公约数中最大的称为最大公约数。

比如：

????????20的约数有1，2，4，5，10，20；

? ? ? ? 15的约束有1，3，5，15；

20和15的公约数有1和5；

则20和15的最大公约数为5；

辗转相除法（欧几里得算法）

在学习辗转相除法之前需要先理解最大公因数的求法：

? ? ? ? 如果c能够整除a，b那么c同样可以整除（ax+by）比如：5能够整除15和20，所以可以整除85（15*3+20*2)，同样的5可以整除5（20-15）；

? ? ? ? 这个例子可能不够直观432和243的最大公约数是27，243 和 189（432 - 243）的最大公约数也是27，189 和 54（243 - 189）的最大公约数也是27，135（189 - 54）和 54的最大公约数也是27，81（135 - 54） 和 54的最大公约数也是27，最后会剩下54和27（81 - 54），54 - 27最后会的到27。

运算步骤有：

? ? ? ? 432 - 243 = 189

? ? ? ? 243 - 189 = 54

? ? ? ? 189 - 54 = 135

? ? ? ? 135 - 54 = 81

? ? ? ? 81 - 54 = 27

? ? ? ? 54 - 27 = 27

? ? ? ? 中间有重复减去54的步骤，可以简化为189%54 = 27。普通的减法也可以改为%；

? ? ? ? 因为都是重复的运算可以用while循环或者递归完成这系列操作

? ? ? ? 如果把递归（循环）的跳出条件是两个数字中其中一个数字为0的话最后的全部运算步骤就为：

? ? ? ? 432%243 = 189? ? ? ? a = 432 b = 243

? ? ? ? 243%189 = 54? ? ? ? ? a = 243 b = 189

? ? ? ? 189%54 = 27? ? ? ? ? ? a = 189 b = 54

? ? ? ? 54%27 = 0? ? ? ? ? ? ? ? a = 54? ?b = 27

? ? ? ? 27%0 =? ? ? ? ? ? ? ? ? ? ?a = 27? ? b = 0? ? ? ? 此步骤b = 0所以跳出递归（循环），剩下的数字a即为432和243的最大公约数27；

代码实现

核心代码：

int gcd(int a,int b)
{
	if(b == 0)
		return a;
	else
		return gcd(b,a%b);
}

简化代码：

int gcd(int a, int b) {
    return (b==0) ? a : gcd(b, a % b);
}

完整代码：

#include<iostream>
using namespace std;

int gcd(int a,int b)
{
	return (b == 0)?a:gcd(b,a%b);
}

int main()
{
	int a,b;
	cin >> a >> b;
	cout << gcd(a,b);
	return 0;
}