13 最大公约数

题目来源和说明

2011年哈尔滨工业大学计算机研究生机试真题

题目描述

输入两个正整数，求其最大公约数

样例

输入

49 14

输出

7

简要分析

要求a和b的最大公约数： （1）如果a和b全为0，则他们的最大公约数不存在 （2）如果a和b其中之一为0，则他们的最大公约数为a、b中非零的那个； （3）如果a和b都不为0，则使新a=b，新b=a%b，然后重复该过程。

C++ 代码

递归形式：

#include<iostream>

using namespace std;

int gcd(int a,int b) {
    if(b==0) return a;
    else return gcd(b,a%b);
}

int main() {
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF) {
        printf("%d\n",gcd(a,b)); //最大公约数
    }
    return 0;
}

非递归形式

#include<iostream>

using namespace std;

int gcd(int a,int b) {
    while(b!=0) {
        int t=a%b;
        a=b;
        b=t;
    }
    return a;
}

int main() {
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF) {
        printf("%d\n",gcd(a,b));
    }
    return 0;
}