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

算法简介

抄自百度百科

定理

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

gcd(a,b) = gcd(b,a mod b) //(不妨设a>b 且r=a mod b ,r不为0)

一种证明

a可以表示成a = kb + r（a，b，k，r皆为正整数，且r = a mod b)
假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除。
而r = a - kb，两边同时除以d，r/d=a/d-kb/d，由等式右边可知m=r/d为整数，因此d|r
因此d也是b,a mod b的公约数。
因(a,b)和(b,a mod b)的公约数相等，则其最大公约数也相等，得证。

代码

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

突然想到的

关于除法和因子还有一个小技巧，除法分块：

right = n/(n/left);

得出处于 [ left , right ] 的所有整数做 n 的除数时结果时相同的

常用于莫比乌斯反演

写在最后

数据结构作业上要求伪代码化简分数，拓展一下