求m和n的最大公约数

最大公约数"/>

求m和n的最大公约数

题目:求正整数m和n的最大公约数.

算法:

1. r=m%n,现在有0 ≤ r < n
2. 如果r等于0,最大公约数就是n.
3. 让m=n,n=r,返回步骤1.

原理:

能整除正整数m,n的任何数一定能整除m-qn=r(证明如下),因此整除n和r的任何数必定整除qn+r=m;所以{m,n}的公因子集合和{n,r}的公因子集合是一样的.特别地,{m,n}的最大公因子和{n,r}的最大公因子是一样的.

证明:能整除正整数m,n()的任何数一定能整除m-qn=r.
设:k能整除m,n;
则存在正整数x,y使得:kx=m,ky=n成立;
r=m-qn等价于r=kx-qky;
有r/k=x-qy;
证明完毕.

算法代码:

#include<stdio.h>
int main(){int m=119,n=544;int key=1,mod=0;if(m<=0||n<=0){printf("m或n只能为正整数!\n");return 0;}//tips:优化:添加判断如果m>n,交换m,n的值会优化运算速度 while(true){mod=m%n;if(mod==0){key=n;break;}m=n;n=mod;}printf("最大公约数:%d\n",key);return 0;
}

扩展

求m,n的最小公倍数.

使用上面的方法求出m,n的最大公约数r,最小公倍数就为m*n/r.

证明:设正整数m,n的最大公约数为r,证明m*n/r为m,n的最小公倍数.
由于m,n的最大公约数为r
故正整数m/r,n/r互质
则m/r*n/r*r为m,n的最小公倍数
即m*n/r为m,n的最小公倍数.