（2）最大公约数和最小公倍数

发表时间：2022-03-25来源：网络

一、问题描述

二、问题求解

问题分析：

程序设计：

方法一：（穷举法）

方法二：（辗转相除法（也称欧几里德算法））

方法三：（更相减损法）

一、问题描述

问题：

求m和n的最大公约数和最小公倍数。

实例：

2和4的最大公约数是2，最大公倍数是8

输入：

2 4

输出：

4 8

二、问题求解

问题分析：

（1）最大公约数：（也称最大公因数，最大公因子），指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），求最大公约数有多种方法，常见的有质因数分解法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数。

例如：【12和24】12的约数有：1、2、3、4、6、12；24的约数有：1、2、3、4、6、8、12、24。它们共有的约数为：1、2、3、4、6、12，则12和24的最大公约数为12

（2）最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。整数a，b的最小公倍数记为[a，b]。

例如：【12和24】12的倍数有：12、24、36等；24的约数有：24、48、72等。它们共有的约数为：24、72等，则12和24的最小公倍数为24

（3）最小公倍数和最大公约数的关系：

最小公倍数=m*n/最大公约数

程序设计：

方法一：（穷举法）

思路：先判断出m和n中哪个数字较小，以较小的数为起始因子（i）在[i,1]区间内判断是否满足既被m整除又被n整除，如果不满足，i--（因子减一）重复判断动作，直到找到满足条件的因子，程序结束；如果满足，该因子即为最大公因子，直接结束程序。

#include //计算最大公因子（穷举法） int gcd(int m, int n) { int temp = m > n ? n : m; int res = 1; for (int i = temp; i > =1; i--) { if (m % i == 0 && n % i == 0) { res = i; break; } } return res; } int main() { int m, n; scanf("%d%d", &m, &n); int temp = gcd(m, n); printf("%d %d\n", temp, m * n / temp); }

测试1：

测试2：

方法二：（辗转相除法（也称欧几里德算法））

思路：辗转相除算法：当除数不为0时，将除数m和被除数n进行求余操作，余数temp；然后令m=n;n=temp;继续判断除数n是否为0，重复前面动作，直到除数为0，程序结束。

//计算最大公因子（辗转相除法——非递归） int gcd2_1(int m, int n) { int res = 0; while(n != 0) { int temp = m % n; m = n; n = temp; } res = m; return res; } //计算最大公因子（辗转相除法——递归） int gcd2_2(int m, int n) { if (m % n == 0) return n; else return gcd2_2(n, m % n); }

方法三：（更相减损法）

更相减损法：也叫更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

算法步骤：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则整除2约简，重新判断；若不是则执行第二步。

第二步：以较大的数m减较小的数n得到差temp，接着把所得的差与较小的数n比较，并以大数减小数（将两者中m=较大的数，n=较小的数）。重复步骤二，直到所得的减数和差相等为止。

最大公因数=（第一步约掉的若干个2的乘积）*（第二步中结束时的等数（即差或减数））

int gcd3(int m, int n) { int res1=1, x; while (m % 2 == 0 && n % 2 == 0) //判断m和n能被多少个2整除，并计算若干2的乘积结果为res1 { m /= 2; n /= 2; res1*=2; } //保证m保存较大的值 if (m < n) { int temp = m; m = n; n = temp; } do { x = m - n; m = (n > x) ? n : x; n = (n < x) ? n : x; } while (n != x); if (res1 == 1) return x; else return res1*x; }

上一篇：编程思维需要最简洁的逻辑，程序员要给客户，最简单的解决方案_软件

下一篇：最简单最快速的UG编程入门_加工