求最大公因数的两种方法（高效方法）

2024-07-17 03:58| 来源: 网络整理| 查看: 265

给定两个数，例如 a = 27 , b = 12 a=27, b=12 a=27,b=12，我们知道a, b的最大公因数为3。下面将介绍两种求最大公因数的高效方法：

（1）辗转相除法

辗转相除法有一个高大上的名字：欧几里得法。下面模拟辗转相除法求a, b的最大公因数：

Created with Raphaël 2.2.0 开始 a = 27, b = 12 c = a%b a = b, b =c b=0？输出最大公因数a 结束 yes no

辗转相除法的代码如下：这里采用递归，并且是精简形式。

int gcd_1(int a, int b){ return b == 0 ? a:gcd_1(b, a%b); } （2）辗转相减法

辗转相减法也有一个高大上的名字：尼考曼彻斯法。下面模拟辗转相减法求a, b的最大公因数：

Created with Raphaël 2.2.0 开始 a = 27, b = 12 a>b? a = a - b a

【本文地址】

公司简介

联系我们