本文共 1535 字,大约阅读时间需要 5 分钟。
最大公约数(Greatest Common Divisor)指两个或多个整数共有约数中最大的一个。
也称最大公因数、最大公因子,a, b的最大公约数记为(a,b),同样的,a,b,c的最大 公约数记为(a,b,c),多个 整数的最大公约数也有同样的记号。求最大公约数有多种 方法,常见的有 质因数分解法、 短除法、 辗转相除法、 更相减损法。与最大公约数相对应的概念是 最小公倍数,a,b的 最小公倍数记为[a,b]。
再来介绍一下辗转相除法:
辗转相除法又叫欧几里得算法,是欧几里得最先提出来的.辗转相除法的实现,是基于下面的原理(在这里用(a,b)表示a和b的最大公因数): (a,b)=(a,ka+b),其中a、b、k都为自然数.………………① 也就是说,两个数的最大公约数,将其中一个数加到另一个数上,得到的新数,其公约数不变,比如(4,6)=(4+6,6)=(4,6+2×4)=2.要证明这个原理很容易:如果p是a和ka+b的公约数,p整除a,也能整除ka+b.那么就必定要整除b,所以p又是a和b的公约数,从而证明他们的最大公约数也是相等的. 基于上面的原理,就能实现我们的迭代相减法: (78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2 基本上思路就是大数减去小数,一直减到能算出来为止,在作为练习的时候,往往进行到某一步就已经可以看出得值.迭代相减法简单,不过步数比较多,实际上我们可以看到,在上面的过程中,由(78,14)到(8,14)完全可以一步到位,因为(78,14)=(14×5+8,14)=(8,14),由此就诞生出我们的辗转相除法. 用辗转相除法求(a,b).设r0=b,r1=a,反复运用除法算式,得到一系列整数qi,ri和下面的方程: 相当于每一步都运用原理①把数字进行缩小,上面右边就是每一步对应的缩小结果,可以看出,最后的余数rn就是a和b的公约数.迭代相减法和辗转相除法在本质上是一样的,相对来说,减法比较简单(需要10步),但是除法步数少(仅需4步).因此可以通过这个原理来求出最大公约数:
#include<iostream> #include<cstdio> using namespace std; int fun(int m,int n){ int rem; //余数,当余数为0的时候,最后的m即为最大公约数 //先用较小的数对较大的数取余,再用余数对较小的数求余,直到余数为零 while(n > 0){ rem = m % n; m = n; n = rem; } return m; //将结果返回 } int main(){ int n,m; cin>>m>>n; cout<<"m和n的最大公约数为:"<<fun(m,n)<<endl; return 0; } 因为到余数为零结束,所以还可以将程序简化一下用递归来求: int fun(int m,int n){ if(n==0) return m; return fun(n,m%n); } 再简化一下,用一行代码来求: int gcd(int m, int n) { return n ? gcd(n, m % n) : m; } ———————————————— 版权声明:本文为CSDN博主「AC-fun」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/qq_41575507/article/details/90752742