欧几里得算法

又名辗转相除法

可在很短时间内计算出非负整数$a$,$b$的最大公因数

就像这样↓

举个栗子

求345，234的最大公因数

345 / 234 = 1 …… 111

234 / 111 = 2 …… 12

111 / 12 = 9 …… 3

12 / 3 = 4 …… 0

所以(345,234)=3

C++实现

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(a%b==0) return b;
    else return gcd(b,a%b);
}
int main(){
    int x,y; 
    cin>>x>>y;
    cout<<gcd(x,y);
    return 0;
}