【经典算法】:欧几里得算法求最大公约数

前言

欧几里得算法就是一个叫做欧几里得的数学家提出来的一种算法用来可以计算两个数的最大的公约数，和最简单的那种枚举不同，这种算法有种巧妙的计算。
当然，我们不是数学家，只是计算机从业者，因此对于算法的详细证明就不说了，就只写写简单的算法

算法核心

算法 gcd(m,n) = gcd(n,m%n); 反复利用这个公式，建立的前提是m>n;
最后结束的条件是 n ==0 ;

代码实现

这里有递归和非递归版本
递归版本：

//// 欧几里得算法求最大公约数
#include <iostream>
using namespace std;
int gcd(int a,int b){
    if(a<b){
        int temp = a;
        a = b;
        b = temp;
    }
    if(b==0) return a;   //结束条件
    else
        return gcd(b,a%b);
}
int main(){
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
}

非递归版本

#include <iostream>
using namespace std;
int gcd(int m,int n){
    if(m<n){
        int temp = m;
        m = n;
        n = temp;
    }
    while(n>0){   //当n == 0 时结果一定能够被计算出来
        int temp = m%n;
        m = n;
        n = temp;
    }
    return m;
}
int main(){
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b)<<endl;
}