最大公约数（Greatest Common Divisor）指两个或多个整数共有约数中最大的一个。
也称最大公因数、最大公因子，a， b的最大公约数记为（a，b），同样的，a，b，c的最大 公约数记为（a，b，c），多个 整数的最大公约数也有同样的记号。求最大公约数有多种 方法，常见的有 质因数分解法、 短除法、 辗转相除法、 更相减损法。与最大公约数相对应的概念是 最小公倍数，a，b的 最小公倍数记为[a，b]。
再来介绍一下辗转相除法：
因此可以通过这个原理来求出最大公约数：
#include
#include
using namespace std; int fun(int m,int n){ int rem; //余数，当余数为0的时候，最后的m即为最大公约数 //先用较小的数对较大的数取余，再用余数对较小的数求余，直到余数为零 while(n > 0){ rem = m % n; m = n; n = rem; } return m; //将结果返回 } int main(){ int n,m; cin>>m>>n; cout<<"m和n的最大公约数为："<
因为到余数为零结束，所以还可以将程序简化一下用递归来求：
int fun(int m,int n){ if(n==0) return m; return fun(n,m%n); }再简化一下，用一行代码来求：
int gcd(int m, int n) { return n ? gcd(n, m % n) : m; }版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/198156.html原文链接：https://javaforall.net
