/*对于已知的两个自然数m, n，假设m>n计算m除以ｎ，将得到的余数记做r如果r=0,则此时的n为求得的最大公约数。否则，将n的值保存在m中，将r的值保存在n中，重复执行下去。*///欧几里得->辗转相除法#include <stdio.h>#include <string.h>#include <math.h>#include <stdlib.h>#include <iostream>#include <iomanip>#include <algorithm>using namespace std;int gcd(int a, int b){    int m, n, r; //m大 n小    if(a>b)    {        m=a; n=b;    }    else    {        m=b; n=a;    }    r=m%n;    while(r!=0)    {        m=n;        n=r;        r=m%n;    }    return n;}int main(){    int n, m, dd;    while(scanf("%d %d", &n, &m)!=EOF)    {        dd=gcd(n, m);        printf("%d\n", dd);    }    return 0;}

/*欧几里得算法的执行效率很高，但是如果参与运算的数据非常大的话就暴露了缺点。计算机中的整数最多是64位，如果低于64位，取模运算比较简单，直接用%就行。但是如果对于计算两个超过64位的整数的模，gcd算法效率十分低，这是便有了Stein算法。*/#include <stdio.h>#include <string.h>#include <math.h>#include <stdlib.h>#include <iostream>#include <iomanip>#include <algorithm>using namespace std;int Stein(int a, int b){    int m, n, r;    if(a>b)    {        m=a; n=b;    }    else    {        m=b; n=a;    }    if(n==0)      return m;    if(m%2==0 && n%2==0 )    {        return 2*Stein(m/2, n/2);    }    if(m%2==0)      return Stein(m/2, n);    if(n%2==0)      return Stein(m, n/2);    return Stein((m+n)/2, (m-n)/2);}int main(){    int n, m, dd;    while(scanf("%d %d", &n, &m)!=EOF)    {        dd=Stein(n, m);        printf("%d\n", dd);    }    return 0;}