数学中两个数如何求最大的公约数（求两个数的最大公约数的三种方法算法）

题目：给定两个正整数m和n（m>n），求它们的最大公因数，现在小编就来说说关于数学中两个数如何求最大的公约数?下面内容希望能帮助到你，我们来一起看看吧!

数学中两个数如何求最大的公约数

题目：给定两个正整数m和n（m>n），求它们的最大公因数。

第一种解法：辗转相除法（欧几里得算法）

算法描述：

步骤1：用m除以n，得余数r；

步骤2：若r=0？算法终止，n是答案；

步骤3：置m=n，n=r；返回步骤1；

算法流程图：

程序如下：

算法效率分析：当数据增大n倍时，该算法执行次数是增加logn次，所以该算法时间复杂度为O(logn),在实际工程应用中是值得推荐的。

第二种解法：辗转相减法

算法描述：

步骤1：判断m和n是否相等，若相等算法终止，m是答案；

步骤2：若m>n? ；则m= m-n否则n=n-m；返回步骤1；

算法流程图：

程序如下：

算法效率分析：该算法时间复杂度为O(logn)，在实际工程应用中也是值得推荐的。

第三种解法：辗转枚举法

算法描述：

步骤1：置ret = n；

步骤2：若m %ret=0 ？且n%ret=0？算法终止，ret是答案，否则ret减一，

重复步骤2；

算法流程图：

程序如下：

算法效率分析：该算法时间复杂度为O(n)，在实际工程应用中不值得推荐的。

请关注“程序猿的自我修炼”，我们一起来修炼吧，成为中心的大神！