一、最大公约数
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）《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，原文是：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
【方法2】：求两个整数的最大公约数可以采用辗转相除法即欧几里德算法。对于任意两个自然数m和n，用m，n，r分别表示被除数、除数、余数，那么m和n的最大公约数等于n和r的最大公约数。以下是辗转相除法的算法： 1)求m除以n的余数r； 2)当r!=0,执行第3)步；若r==0，则n为最大公约数,算法结束。 3)将n的值赋给m，将r的值赋给n；再求m除以n的余数r。 4)转到第2)步 【参考程序】 #include <iostream> using namespace std; int main () { int m,n; cin>>m>>n; int r =m % n; while (r!=0) //也可以使用 while (r),c++中 非0即真 { m=n; n=r; r=m % n; } cout<<"最大公约数="<<n<<endl; return 0; }
例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】二进制最大公约数算法： (1)递归终止条件：gcd(m,m)=m。 (2)递归关系式： m<n时：gcd(m,n)=gcd(n,m) m为偶数，n为偶数：gcd(m,n)=2*gcd(m/2,n/2) m为偶数，n为奇数：gcd(m,n)=gcd(m/2,n) m为奇数，n为偶数：gcd(m,n)=gcd(m,n/2) m为奇数，n为奇数：gcd(m,n)=gcd(n,m-n) 该方法和方法1相比更适合求高精度数的最大公约数，因为只涉及除2和减法操作，而辗转相除法则需要用到高精度除法。 程序如下： #include<iostream> using namespace std; int gcd(int m,int n) { if(m==n)return m; //递归终止条件 if(m<n)return gcd(n,m); if(m%2==0) { if(n%2==0) return 2*gcd(m/2,n/2); //m为偶数，n为偶数 else return gcd(m/2,n); //m为偶数，n为奇数 } else { if(n%2==0) return gcd(m,n/2); //m为奇数，n为偶数 else return gcd(n,m-n); //m为奇数，n为奇数 } } int main() { int m,n; cin>>m>>n; cout<<gcd(m,n)<<endl; return 0; }
说明：以上内容参考百度、信息学奥赛一本通，仅限于自己内部使用，帮助理解最大公约数。
标签：12,gcd,int,......,最大公约数,余数 From： https://www.cnblogs.com/ddfy198811/p/17021043.html