正解是使用辗转相除法，该方法你们在数学必修三应该都学过，就不赘述具体步骤了

质因数分解不能过本题，这是因为质因数分解的时间复杂度是 O(\sqrt n) ，即假设真的是一个质数，起码要遍历到 \sqrt n 次才能结束循环

注意这题卡 long long ，所有相关的变量都应该设为 long long

热知识： 编译器自带 __gcd 函数。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
signed main()
{
    cin >> a >> b;
    cout << gcd(a, b);
    return 0;
}