808. 最大公约数

Question

输入两个整数 a 和 b，请你编写一个函数，int gcd(int a, int b), 计算并输出 a 和 b 的最大公约数。

输入格式
共一行，包含两个整数 a 和 b。

输出格式
共一行，包含一个整数，表示 a 和 b 的最大公约数。

数据范围
1≤a,b≤1000
输入样例：
12 16
输出样例：
4

Ideas

Code

#include 

using namespace std;

int gcd(int a, int b)
{
    if (a < b) swap(a,b);
    for (int i = b; i; i --)
    {
        if (a % i == 0 && b % i == 0)
            return i;
    }
}

int main()
{
    int a,b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22