如果不想看证明,只想直接用的话。只用记住x=__gcd(m,n),x的值即为m和n的最大公约数。
lcm(最大公约数)*gcd(最小公倍数)=m*n。__gcd()函数在头文件algorithm里面。
了解最大公约数前我们先了解什么是约数。约数也叫因数。
约数是指整数a除以整数b所得的商正好为一个整数,那么称a为b的倍数,b为a的约数。
比如a=6,那么他的约数就是1,2,3,6。a=9,a的约数为1,3,9。了解了约数的话,最大公约数就顾名思义了,
意思就是多个整数公共的约数。比如求15和12,15的约数有1,3,5,15。12的约数有1,2,3,4,6,12。
他们公共且最大的约数即为3。
求两个整数最大公约数主要的方法:
1.穷举法:分别列出两整数的所有约数,并找出最大的公约数。
2.素因数分解:分别列出两数的素因数分解式,并计算共同项的乘积。
3.短除法:两数除以其共同素因数,直到两数互素时,所有除数的乘积即为最大公约数。
4.辗转相除法:两数相除,取余数重复进行相除,直到余数为0时,前一个除数即为最大公约数。
下面只介绍个别几种方法。
一、穷举法
顾名思义,求出两个数所有的约数然后取最大的约数即可。
#include<stdio.h>
int main()
{
int m,n,i;
scanf("%d",&m);
scanf("%d",&n);
for(i=m;i>=1;i--)
if(m%i==0 && n%i==0)
break;
printf("%d\n",i);
return 0;
}
二、辗转相除法,也叫欧几里得算法。
用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。最后所得的那个最大公约数,就是所有这些数的最大公约数。
下面是第一种写法
int gcd(int a,int b)
{
int temp;
while(b)
{
/*利用辗除法,直到b为0为止*/
temp = b;
b = a % b;
a = temp;
}
return a;
}
第二种写法
int gcd(int m, int n)
{
return n? gcd(n,m%n) : m;
}
看懂上面的代码需要我们先理解为什么gcd(m,n) = gcd(n, m mod n)。
知识补充,k|a的意思为,a能被k整除。即a=qk。q为整数
一个常识,如果 a≥b 并且 b≤a,那么 a=b。
一个前提,讨论的数均大于等于0。
一个引理
假设 k|a, k|b,则对任意的 x,y ∈ Z, k|(xa+yb)均成立.
证明:
k|a => a=pk, k|b => b==qk (其中 p,q ∈ Z)
于是有 xa+yb=xpk+yqk=(xp+yq)k
因为 k|(xp+yq)k, 所以 k|(xa+yb)
gcd算法证明
命题:对任意 m, n ∈ N,证明gcd(m,n) = gcd(n, m mod n)
证明:
令 k=gcd(m,n),则 k|m 并且 k|n;
令 j=gcd(n, m mod n), 则j|n 并且 j|(m mod n);
对于m, 可以用n 表示为 m=pn+(m mod n);
由引理可知 j|m==j|pn+(m mod n)(其中 x=p,y=1), 又 j|n,于是 j 是 m 和 n 的公约数(但不一定是最大的);
因为 k 是 m 和 n 的最大公约数,所以必有 k≥j;
通过另一种表示形式:(m mod n)=m-pn,同理可得:
k|(m mod n)==k|m-pn(x=1,y=-p),又k|n,于是 k 是 (m mod n) 和 n 的公约数(也不一定是最大的);
同样由 j 是 n 和 (m mod n) 的最大公约数可以得到 j≥k;
由常识,得出结论 k=j,
即gcd(m,n) = gcd(n, m mod n) ,得证。
int gcd(int m, int n)
{
return n? gcd(n,m%n) : m;
}
这个算法不用纠结m和n谁打谁小,结果是一样的。
n!=0时,根据上面的证明,gcd(m,n)和gcd(n,n%m)相等。一直递归,因为是取余的操作,所有到m%n==0时,返回此时的m即可。
三、运用库函数。
这种方法最简单,__gcd()即可。
写算法还是直接用__gcd比较好。
证明来源 https://www.cnblogs.com/ider/archive/2010/11/16/gcd_euclid.html