C++最大公因数、最小公倍数代码实现（比较简单，欧几里得法）

今天给大家带来的代码微课是最大公因数、最小公倍数比较简单的代码实现（10~20行）

原理：利用欧几里得《几何原本》中的计算替换方法

详细讲解：

今天我们所运用的数学方法名曰：更相减损术（欧几里得辗转相除法）

这其实是一种很简便快捷、重要的方法，他可以快速地帮你求两个数的最大公因数。

实际上，对于两个不同的正整数a,b(a > b)，有一个神奇的公式

gcd(a,b) = gcd(a,a - b)

也就是说，a和,b的最大公因数=a-b的最大公因数。

但是，这种方式仍旧有些许繁琐，于是作者简化了一下

gcd(a,b) = gcd(b,a % b);

现在，我们将它简化为一个函数。

int gcd(int x, int y) 
{ 
    while (y > 0)
    {
    	int temp = y;
    	y = x % y;
    	x = temp;
    }
    
    
    return x; 
}

这，就是最大公因数的快捷方式。

接下来我们就来运用它。

#include <iostream>
using namespace std;

​
int gcd(int x, int y) 
{ 
    while (y > 0)
    {
    	int temp = y;
    	y = x % y;
    	x = temp;
    }
    
    
    return x; 
}

​

int main(){
    int a,b;
    cin >> a,b;
    cout << gcd(a,b) << endl;
    return 0;
}

这个草稿存了100多天了，今天给它完结