欧几里得算法求最大公约数

2024-07-11 22:20| 来源: 网络整理| 查看: 265

欧几里得算法求最大公约数

欧几里得算法是一个非常经典的算法，它的基本步骤如下：

给定两正整数m，n选取其中较小的数，假定为m若n%m非0，即存在余数，将n和m中较大的数n替换为余数，返回步骤2若n%m为0，则最大公约数为m

直观上看，可以这样理解欧几里得算法：

“辗转相除法的演示动画：两条线段长分别可表示252和105，则其中每一小分段长代表最大公约数21。如动画所示，只要辗转地从大数中减去小数，直到其中一段的长度为0，此时剩下的一条线段的长度就是252和105的最大公因数。” 在这里插入图片描述

“算法的演示动画。最初的绿色矩形的长和宽分别是a = 1071、b = 462，从中不断铺上462×462的正方形直到剩下部分面积是462×147；然后再铺上147×147的正方形直至剩下21×147的面积；最后，铺上21×21的正方形时，绿色部分就没有了。即21是1071和462的最大公约数” 在这里插入图片描述

c++代码实现：

//输入:两个正整数m,n //输出:m，n的最大公约数 int gcd(int m,int n){ if(m%n==0) return n; if(n%m==0) return m; if(m>=n) return gcd(n,m%n); else return gcd(m,n%m); } //输入:两个正整数m,n //输出:m，n的最大公约数 //默认m>n,即使不是，经过一次循环之后也可满足 int gcd(int m,int n){ return n==0?m:gcd(n,m%n); } //输入:两个正整数m,n //输出:m，n的最大公约数 //默认m>n,即使不是，经过一次循环之后也可满足 //非递归实现 int gcd(int m,int n){ int t = 0; while(n!=0){ t = n; n = m%n; m = t; } return m; }

时间复杂度分析：https://blog.csdn.net/ZeroOnet/article/details/53375313

【本文地址】

公司简介

联系我们