一、最大公约数
1、定义：最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。
例如：12、16的公约数有1、2、4，其中4就是12、16的最大公约数。
二、求解方法
1、朴素算法：从m、n较小的一个数开始枚举，如果都能被m、n整除，那么该数就是两数的最大公约数，否则继续减一，直至枚举到1为止。（这个算法复杂度十分不优秀，只是帮助大家理解如何求最大公约数，彰显辗转相除算法的优秀）。
例如：求12、8的最大公约数
解：先枚举8 12/8=1……4 8/8=1……0
7 12/7=1……5 8/7=1……1
6 12/6=2……0 8/6=1……2
5 12/5=2……2 8/5=1……3
4 12/4=3……0 8/4=2……0
因此最大公约数为4。
例1 求两个正整数ｍ，ｎ的最大公约数。
【方法1】：求任意两个自然数m和n的最大公约数，可以想到其最大的可能就是两个数中的较小者min，最小可能是1。所以，可以设最大公约数gcd从min开始进行判断，若gcd>1并且没有同时整除m和n，那么就gcd-1，重复判断是否整除。
【参考程序】
#include<iostream>
using namespace std;
int main()
{
int m,n,gcd;
cin>>m>>n;
gcd=m>n?n:m; //注意此处的特殊写法
while (gcd>1&&(m%gcd!=0||n%gcd!=0))
gcd–; //每次减1寻找最大公约数
cout<<gcd<<endl; //输出最大公约数
return 0;
}
2、更相减损术
（1）《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，原文是：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
该方法和方法1相比更适合求高精度数的最大公约数，因为只涉及除2和减法操作，而辗转相除法则需要用到高精度除法。
【方法2】：求两个整数的最大公约数可以采用辗转相除法即欧几里德算法。对于任意两个自然数m和n，用m，n，r分别表示被除数、除数、余数，那么m和n的最大公约数等于n和r的最大公约数。以下是辗转相除法的算法： 1)求m除以n的余数r；
例4 用递归方法求两个数m和n的最大公约数。(m>0，n>0)
【方法1】求两个数的最大公约数，可以用枚举因子的方法，从两者中较小的数枚举到能被两个数同时整除且是最大的约数的方法；也可以用辗转相除法，这里采用递归实现辗转相除算法：
①求m除以n的余数;
②如果余数不为0，则让m=n，n=余数，重复步骤①，即调用子程序;
③如果余数为0，则终止调用子程序;
④输出此时的n值。
#include<iostream>
using namespace std;
int gcd(int,int);
int main()
{ int m,n;
cin>>m>>n;
cout<<” gcd=”<<gcd(m,n)<<endl;
return 0;
}
int gcd(int m,int n)
{
return m%n==0?n:gcd(n,m%n);
}
【方法2】二进制最大公约数算法：
说明：以上内容参考百度、信息学奥赛一本通，仅限于自己内部使用，帮助理解最大公约数。
今天的文章最大公约数分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/55320.html
