欧几里得算法（辗转相除法）——求最大公约数

首先要明确一个概念：什么是最大公约数？

顾名思义：就是两个数中公共的约数中最大的一个呗
例如：

• 12 的约数有：1 2 3 4 6 12
• 8 的约数有 ：1 2 4 8
  则称8和12的最大公约数为：4，记作：(12,8)=4

一般的 （a,b) = c，则称a和b的最大公约数为c // GCD(a,b) = c也表示这个意思

• 如果GCD(a,b）= 1，则称a和b互素
• a和b互素和a和b是否为质数没关系，如(6,35)=1，但6和35都不是素数

欧几里得算法内容：两个数的最大公约数==较小的那个和两数相除余数的最大公约数

• 举个简单例子:

 						 GCD(252,105) // 252 = 2*105 + 42= GCD(105,42) // 105 = 42*2 +21 = GCD(42,21) // 42 = 21*2 + 0= GCD(21,0)= 21 

欧几里得算法几何法说明（需翻墙）

小朋友，你是不是有很多问号？？？？？？？？？

• 下面我们来证明一下：

证: 我们首先假设"g"为自然数"a","b"的最大公因数(a>b),"m","n"为任意自然数则有 g = (a,b) , a = mg , b = ng则有 g = (mg,ng) , a%b = m%n而	g = (mg,ng) 又等于 g = (ng,m%ng)=(b,a%b)证毕	

欧几里得算法代码实现：

// 迭代法
int GCD(int max,int min) 
{
    while (min != 0) {
    int num = max % min;max = min;min = num;	}return min;
}

// 递归法
int GCD(int max,int min)
{
    if (min == 0) return min;return GCD(min,max%min);
}