题目描述

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。

算法:

一、辗转相除法， 又名欧几里德算法（Euclidean algorithm）

其算法过程为：设两数为a,b设其中a 做被除数,b做除数，temp为余数

a、大数放a中、小数放b中；

b、求a/b的余数；

c、若temp=0则b为最大公约数；

d、如果temp!=0则把b的值给a、temp的值给a；

f、返回第二步；

二、穷举法：

穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数

三、更相减损术：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法！

四、Stein算法：

通过数学的思想进行验证出：对于俩个正整数数（x>y）：

均为偶数gcd(x,y)=2gcd(x/2,y/2)；

均为奇数gcd(x,y)=gcd((x+y)/2,(x-y)/2)；

x奇y偶gcd(x,y)=gcd(x,y/2)；

x偶y奇gcd(x,y) =gcd(x/2,y)或gcd(x,y)=gcd(y,x/2)；

五、短除法求最大公约数：

短除法是不断地找两个数的最小公约数，直到找不到为止，然后把所有的最小公约数乘起来，就是最大公约数。

输入格式

输入2个数a,b

输出格式

输出一个数

样例

6 8

2