辗转相除法求两个数的最小公倍数与最大公约数

辗转相除法‎求最大公约‎数和最小公‎倍数1: /*辗转相除法‎基于如下原‎理：两个整数的‎最大公约数‎等于其中较‎小的数和两‎数的差的最‎大公约数。

2: 例如，252和1‎05的最大‎公约数是2‎1（252 = 21 ×12；105 = 21 ×5）；3: 因为252‎? 105 = 147，所以147‎和105的‎最大公约数‎也是21。

在这个过程‎中，较大的数缩‎4: 小了，所以继续进‎行同样的计‎算可以不断‎缩小这两个‎数直至其中‎一个变成零‎。

这时，所剩下的5: 还没有变成‎零的数就是‎两数的最大‎公约数。

6: */7: #inclu‎d e <stdio‎.h>8:9: int getGC‎D AndL‎C M(int a,int b){10: int max=a>b?a:b;//将较大的数‎赋给max‎11: int min=(max=a)?b:a;//将较小的数‎赋给min‎12: int temp;//暂时存储变‎量13: while‎(max!=0){14: temp=min%max;15: min=max;16: max=temp;17: }18: print‎f("最大公约数‎为%d\n",min);19: print‎f("最小公倍数‎为%d\n",a*b/min);20: }21:22: int main(){23: print‎f("输入两个数‎整数值\n");24: int a,b;25: scanf‎("%d",&a);26: scanf‎("%d",&b);27: getGC‎D AndL‎C M(a,b);28: retur‎n0;29: }C语言水仙‎花数算法打印出所有‎的“水仙花数”，所谓“水仙花数”是指一个三‎位数，其各位数字‎立方和等于‎该数本身。

求最大公倍数的方法
求最大公倍数的方法有多种，以下列举几种常用的方法：
1.因数分解法：将两个数进行因数分解，然后将两个数的所有公因数相乘，得到的结果即为最大公倍数。

2.辗转相除法：先求两个数的最大公约数，然后用两个数相乘除以最大公约数，得到的结果即为最大公倍数。

3.列表法：将两个数的所有倍数列出来，然后找到两个数相同的倍数，最小的那个即为最大公倍数。

4.质因数法：将两个数进行质因数分解，然后将两个数所有的质因数相乘，得到的结果即为最大公倍数。

这些方法在不同情况下适用，根据具体问题的要求选择相应的方法求解最大公倍数。

编辑本段证明简单的想法设两数为a、b(b＜a)，求它们最大公约数(a，b)的步骤如下：用b除a，得a＝bq......r 1(0≤r)。

若r1=0，则(a，b)＝b；若r1≠0，则再用r1除b，得b＝r1q......r2 (0≤r2).若r2＝0，则(a，b)＝r1，若r2≠0，则继续用r2除r1,……如此下去，直到能整除为止。

其最后一个非零余数即为(a，b)。

原理及其详细证明在介绍这个方法之前，先说明整除性的一些特点（下文的所有数都是正整数，不再重覆），我们可以这样给出整除性的定义：对于二个自然数a和b，若存在正整数q，使a=bq，则a能被b整除，b为a的因子，a为b的倍数。

如果a能被c整除，并且b也能被c整除，则c为a、b的公因数（公有因数）。

由此我们可以得出以下推论：推论1、如果a能被b整除（a=qb），若k为正整数，则ka也能被b整除（ka=kqb）推论2、如果a能被c整除（a=hc），b也能被c整除（b=tc），则(a±b)也能被c整除因为：将二式相加：a+b=hc+tc=(h+t)c 同理二式相减：a－b=hc－tc=(h －t)c所以：(a±b)也能被c整除推论3、如果a能被b整除（a=qb），b也能被a整除（b=ta），则a=b 因为：a=qb b=ta a=qta qt=1 因为q、t均为正整数，所以t=q=1 所以：a=b辗转相除法是用来计算两个数的最大公因数，在数值很大时尤其有用，而且应用在电脑程式上也十分简单。

其理论如下:如果 q 和 r 是 m 除以 n 的商及余数，即 m=nq+r，则gcd(m,n)=gcd(n,r)。

证明是这样的: 设 a=gcd(m,n)，b=gcd(n,r)证明：∵a为m,n的最大公约数，∴m能被a整除，且n也能被a整除，∴由推论1得：qn也能被a整除，∴ 由推论2得：m-qn也能被a整除，又∵m-qn=r，∴r也能被a整除，即a为n和r的公约数（注意：还不是最大公约数）∵b为n和r的最大公约数，a为n和r的公约数∴a≤b，同理∵b为n, r的最大公约数，∴n能被b整除，且r也能被b整除，∴由推论1得：qn也能被b整除，∴由推论2得：qn+r也能被b整除，又∵m=qn+r，∴m也能被b整除，即b为m和n的公约数，（注意：还不是最大公约数）∵a为m,n的最大公约数，b为m和n的公约数，∴b≤a，由以上可知：a≤b与b≤a同时成立，故可得a=b，证毕。

辗转相除法求最大公约数和最小公倍数最大公约数和最小公倍数是初中数学中的重要概念，它们在数学、物理、化学等领域中都有广泛的应用。

本文将介绍一种求最大公约数和最小公倍数的方法——辗转相除法。

一、最大公约数最大公约数指的是两个或多个整数共有的约数中最大的一个。

例如，12和18的最大公约数是6，因为12和18的公约数有1、2、3、6，其中6最大。

求最大公约数最常用的方法是质因数分解法，但这种方法在数比较大时会比较麻烦。

辗转相除法是一种简便的方法。

1. 辗转相除法的基本思想辗转相除法的基本思想是：用较大的数去除较小的数，再用余数去除除数，如此反复，直到余数为0为止。

最后的除数就是这两个数的最大公约数。

例如，求12和18的最大公约数，可以按下面的步骤进行：（1）用18除12，得商1余6；（2）用12除6，得商2余0。

因为余数为0，所以6就是12和18的最大公约数。

2. 辗转相除法的证明辗转相除法的正确性可以用数学归纳法来证明。

假设a、b都是正整数，且a>b。

（1）当b=0时，a就是a和b的最大公约数。

（2）当b≠0时，假设r是a÷b的余数，即a=bq+r（q是a÷b 的商，r<b）。

设d是b和r的最大公约数，根据带余除法，可以得到a和b的最大公约数等于b和r的最大公约数，即gcd(a,b)=gcd(b,r)。

根据归纳法的假设可知，gcd(b,r)也可以用辗转相除法求得。

因此，gcd(a,b)也可以用辗转相除法求得。

3. 辗转相除法的优点辗转相除法与质因数分解法相比，具有以下优点：（1）速度快：辗转相除法只需要进行简单的除法运算，而质因数分解法需要进行较多的乘法和除法运算，所以辗转相除法更快。

（2）适用范围广：辗转相除法可以用于任意大小的数，而质因数分解法只适用于比较小的数。

二、最小公倍数最小公倍数指的是两个或多个数公有的倍数中最小的一个。

例如，4和6的最小公倍数是12，因为4的倍数有4、8、12、16、20、24、28……，6的倍数有6、12、18、24、30、36、42……，它们公有的倍数有12、24、36……，其中12最小。

求最小公倍数的方法
最小公倍数是指两个或多个数共有的倍数中最小的那个数。

求解最小公倍数的方法有以下几种。

1. 列举法：列举出两个或多个数的倍数，找到它们共有的最小倍数。

这种方法适用于较小的数。

2. 分解质因数法：将每个数分解质因数，然后取每个质因数的最高指数相乘，得到最小公倍数。

3. 短除法：使用短除法求得两个或多个数的素因子分解，然后将每个数中出现的所有素因子按照最高指数相乘，得到最小公倍数。

4. 辗转相除法：对于两个数a和b，先求它们的最大公约数gcd(a,b)，然后将a和b相乘，再除以最大公约数，得到最小公倍数。

5. 使用公式：对于两个数a和b，最小公倍数等于它们的乘积除以最大公约数，即最小公倍数 = (a * b) / gcd(a, b)。

这些方法可以灵活运用，选择适合自己的方法来求解最小公倍数。

辗转相除法求两个整数的最⼤公约数2020新年年初，⼀场疫情让⼈们⽌住了匆忙的脚步。

⼀次在家看初中的在线教育视频，数学课上⽼师讲到⼀种求两个正整数的最⼤公约数的算法：辗转相除法，当时⽼师讲的很好，⾮常易懂，有了理论基础于是想⽤代码的⽅式实现。

以下证明过程与教学视频⽆关。

⼀，辗转相除法「辗转相除法」⼜叫做「欧⼏⾥得算法」,是公元前 300 年左右的希腊数学家欧⼏⾥得在他的著作《⼏何原本》提出的.利⽤这个⽅法,可以较快地求出两个⾃然数的最⼤公因数,即 HCF 或叫做 gcd.所谓最⼤公因数,是指⼏个数的共有的因数之中最⼤的⼀个,例如 8 和 12 的最⼤公因数是 4,记作 gcd(8,12)=4.在介绍这个⽅法之前,先说明整除性的⼀些特点,注以下⽂的所有数都是正整数,以后不再重覆.我们可以这样给出整除以的定义:对於两个⾃然数 a 和 b,若存在正整数 q,使得 a=bq,则 b 能整除 a,记作 b | a,我们叫 b 是 a 的因数,⽽ a 是 b 的倍数.那麼如果 c | a,⽽且 c | b,则 c 是 a 和 b 的公因数.由此,我们可以得出以下⼀些推论:推论⼀:如果 a | b,若 k 是整数,则 a | kb.因为由 a | b 可知 ha=b,所以 (hk)a=kb,即 a | kb.推论⼆:如果 a | b 以及 a | c,则 a | (b±c).因为由 a | b 以及 a | c,可知 ha=b,ka=c,⼆式相加,得 (h+k)a=b+c,即 a | (b+c).同样把⼆式相减可得 a | (b-c).推论三:如果 a | b 以及 b | a,则 a=b.因为由 a | b 以及 b | a,可知 ha=b,a=kb,因此 a=k(ha),hk=1,由於 h 和 k 都是正整数,故 h=k=1,因此 a=b.辗转相除法是⽤来计算两个数的最⼤公因数,在数值很⼤时尤其有⽤⽽且应⽤在电脑程式上也⼗分简单.其理论如下:如果 q 和 r 是 m 除以 n 的商及余数,即 m=nq+r,则 gcd(m,n)=gcd(n,r).证明是这样的:设 a=gcd(m,n),b=gcd(n,r)则有 a | m 及 a | n,因此 a | (m-nq)(这是由推论⼀及推论⼆得出的),即 a | r 及 a | n,所以 a | b⼜ b | r 及 b | n,所以 b | (nq+r),即 b | m 及 b | n,所以b | a.因为 a | b 并且 b | a,所以 a=b,即 gcd(m,n)=gcd(n,r).例如计算 gcd(546,429),由於 546=1(429)+117,429=3(117)+78,117=1(78)+39,78=2(39),因此gcd(546,429)=gcd(429,117)=gcd(117,78)=gcd(78,39)=39最⼩公倍数就是2个数的积除以最⼤公约数框图如下⼆，Java算法实现有了以上的理论基础，算法实现不难，⽤⼀个递归就可以实现，代码如下1public Integer GDC(Integer m, Integer n) {2if (m < n)3 XOR(m, n);45 Integer r = m % n;6if (r > 0) {7return GDC(n, r);8 } else {9return n;10 }11 }1213/**14 * 两个数对换15*/16private void XOR(Integer m, Integer n) {17 m = m ^ n;18 n = m ^ n;19 m = m ^ n;20 }这段代码可以很好的实现求最⼤公约数。

辗转相除找公约数的原理
辗转相除法，也称欧几里得算法，是一种求最大公约数的算法。

该算法基于如下定理：
定理：两个整数a，b（a>b）的最大公约数等于b和a%b（余数）的最大公约数。

例如，求48和18的最大公约数，可以按照下面的步骤进行：
48÷18=2·12
18÷12=1·6
12÷6 =2·0
因为最后的余数为0，所以6是48和18的最大公约数。

可以看到，在每一步中，我们都是将较大的数除以较小的数，并得到一个余数，然后将较小的数和余数作为新的两个数继续进行相同的操作，直到余数为0为止。

最终得到的较小的数就是原来两个数的最大公约数。

这个算法的原理可以用数学归纳法证明。

具体可以参考相关的数学教材和理论知
识。

求最小公倍数的十种方法
1. 最大公约数法：通过求两个数之间的最大公约数，然后将其乘以另外一个数，就可以得到他们的最小公倍数。

2. 列出所有的倍数法：将两个数按照顺序列出所有的倍数，然后从中找出第一个其中有两个数相同的即可。

3. 公式法：LCM（a,b）=a×b/GCD（a,b），用最大公约数法所求出的GCD乷加a和乷即可得到最小公倍数。

4. 二进制法：通过将两个数都转换成二进制的形式在比较，当它们的二进制形式最高位一致时，它们的最小公倍数就相等了。

5. 相乘法：将两个数相乘得到一个新的数，这个新的数就是他们的最小公倍数。

6. 辗转相除法：将两个数由大到小进行按照辗转相除的方式来进行，将最后的结果乘以被除数，就可以得到它们的最小公倍数。

7. 最小正数法：找出两个数之间的最小正数，它们之中肯定存在一个正数的情况，它就是他们的最小公倍数。

8. 差值法：先求出两个数的差值，然后将差值一口气加倍，直到它们大于等于之前那两个数，然后这个差值就是它们的最小公倍数。

9. 化简法：将两个数进行化简，化简成最简分数形式以后，得出分母是它们的最小公倍数。

10. 约分法：将两个数进行约分，然后将约分以后的结果相乘，这个结果就是它们的最小公倍数。

C语言最大公约数与最小公倍数在C语言中，可以使用欧几里得算法（辗转相除法）来计算两个数的最大公约数（GCD），然后使用最大公约数和两数乘积的关系计算最小公倍数（LCM）。

#include <stdio.h>// 定义辗转相除法函数，计算最大公约数int gcd(int a, int b) {if (b == 0) {return a;} else {return gcd(b, a % b);}}// 计算最小公倍数，使用最大公约数和两数乘积的关系int lcm(int a, int b) {return (a * b) / gcd(a, b);}int main() {int num1, num2;printf("请输入两个整数：");scanf("%d %d", &num1, &num2);printf("最大公约数为：%d\n", gcd(num1, num2));printf("最小公倍数为：%d\n", lcm(num1, num2));return 0;}在上述示例中，我们首先定义了辗转相除法的函数gcd，用于计算最大公约数。

然后，我们使用最大公约数和两数乘积的关系，定义了计算最小公倍数的函数lcm最后，我们在main函数中从用户输入读取两个整数，并调用gcd和lcm函数计算最大公约数和最小公倍数，并将结果打印输出。

示例程序的输出如下：请输入两个整数：18 24最大公约数为：6最小公倍数为：72在这个例子中，我们输入了两个整数18和24。

程序计算出它们的最大公约数为6，最小公倍数为72。