3.6 最大公约数

3.6.1 链接地址

http://www.realoj.com/网上第73题

3.6.2 题目内容

求两个正整数的最大公约数。

输入描述：输入数据含有不多于50对的数据，每对数据由两个正整数（0 ＜ n1, n2＜232）组成。

输出描述：对于每组数据n1和n2，计算最大公约数，每个计算结果应占单独一行。

输入样例

        6 5 18 12

输出样例

        1
        6

3.6.3 参考答案

求两数的最大公约数，可采用欧几里得方法：只要两数不相等，就反复用大数减小数，直到相等为止，此相等的数就是两数的最大公约数。

        #include <iostream>
        #include <fstream>

       using namespace std;
        //声明gcd函数，该函数用来计算两数的最大公约数
        int gcd(int, int);
        int main(int argc, char * argv[])
        {
          ifstream cin("aaa.txt");
            int x, y;
            while(cin>>x>>y)
            {
              cout<<gcd(x, y)<<endl;
            }
          return 0;
        }
        int gcd(int x, int y)
        {
            while(x! =y)
            {
              if(x>y)x=x-y;
              else
                    y=y-x;
            }
            return x;
        }