求最大公约数[易语言源码]

求最大公约数易语言源码最大公约数，也称最大公因数、最大公因子是指两个或多个整数共有约数中最大的一个。
我将用多种方法计算出两个数的最大公约数
对两个整数a和b，共同的约数在1到min(a,b)[也就是求a和b哪个小]之间，从大到小枚举，若判断它能同时整除a和b两个数，即为两个数的最大公约数
解释：a%i表示a除i的余数，a%i=0就是a能被i整除，即a是i的倍数或i是a的倍数。
这个算法的最坏时间复杂度为O(min(a,b))

从数学上讲使用方法1的分解质因数的方法，可以令我们从另一方面加深对公约数的理解。例如：a=24，b=60时，对a和b分解质因数得到：
a=2*2*2*3
b=2*2*3*5
收集共有的质因数是2、2、3，得到的最大公约数为：2*2*3=12

解释：由于有i*i<=min（a,b）的优化，时间复杂度降为O(sqrt(min(a,b)))。循环完后，a和b有一个可能没分解完，要注意收集到gcd中，这个算法也可以看成是短除法的变形 我们在方法1采用了低效的算法——枚举法。下面让我们尝试用数学知识找到一种更好的算法！ 假设c是a和b的最大公约数（假设a>b)，那么有a%c=0，且，b%c=0，则（a-b)%c=0亦成立，即若c是b和a-b的公约数，c亦是a和b的公约数。两个公约数集合相等，两个集合中的
最大数也必然相等，简单讲就是：gcd（a，b）=gcd（b，a-b）。
因此我们可以采用函数进迭送，当迭到a=b时，a为a和b的最大公约数，即答案
用《九章算术》中的“更相减损法”求正整数a和b的最大公约数，即答案

这个算法很简洁！但可惜的是效率依然可能较低，比如说a很大，b很小时。那么我们是否可以再加以优化呢？
可以用方法3类似的方法证明：gcd(a,b)=gcd(b,a%b)(a>b)。
这样的话，我们就可以设计出一个更为高效的算法——欧几里德算法。

欧几里德算法的时间复杂度是多少呢？a>b时
（1）若b<=a/2，gcd(a,b)变为gcd(b,a%b)，显然规模至少缩小一半。 （2）若b>a/2，a%b也最少缩小为a的一半。
总之进过一次迭代，gcd(a,b)的数据规模至少会变成原来的一半，所以这个算法的时间复杂度是O(lonN)。