GCD最大公约数

给出a，b

求a和b最大公约数

a是由b的倍数+余数1得到的

辗转相除法

b是由前面的余数1的倍数+余数2得到的

以此类推

直到

余数n为0，余数n-1就是最大公倍数

a = b * 倍数 + p₁;

b = p₁ * 倍数 + p₂;

p₁ = p₂ * 倍数 + p₃；

……

p_n-1=p_n * 倍数+0；

p_n就是最大公约数

下面上代码

#include <stdio.h>
int GCD(int a,int b)
{
    while(b)
    {
        int mid=a;//mid为中间变量
        a=b;
        b=mid%b;
    }
    return a;//a就是最后的最大公约数
}
int main()
{
    int a,b;
    while(~scanf("%d,%d",&a,&b))
        printf("%d
",GCD(a,b));
    return 0;
}