【刷题记录】最大公因数，最小公倍数（辗转相除法、欧几里得算法）

本系列博客为个人刷题思路分享，有需要借鉴即可。

1.题目链接：
无
2.详解思路：
题目描述：输入两个正整数，输出其最大公因数和最小公倍数
一般方法：最大公因数：穷加法；最小公倍数：穷举法。
巧妙方法：最大公因数：辗转相除法；最小公倍数：数学公式。

下面是一般方法的代码示例：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>int main()
{int a = 0;int b = 0;int GreComDiv = 0;scanf("%d %d", &a, &b);int min = a < b ? a : b;int i = 0;//最大公约数——穷加法for (i = 1; i <= min; i++){if (a % i == 0 && b % i == 0)GreComDiv = i;}int lcm = 0;int max = a > b ? a : b;//最小公倍数——穷乘法for (i = 1;; i++){if (((i * max) % a == 0) && ((i * max) % b == 0)){lcm = i * max;break;}}printf("最大公约数为%d 最小公倍数为%d\n", GreComDiv, lcm);return 0;
}

下面是比较巧妙的方法代码示例：

int main()
{int a = 0;int b = 0;scanf("%d %d", &a, &b);int c = a;int d = b;while (a && b){if (a > b)a %= b;elseb %= a;}int max = a > b ? a : b;//最大公因数int min = c * d / max;//最小公倍数printf("最大公约数为%d 最小公倍数为%d\n", max, min);return 0;
}

具体为什么可以这样搞，可以去B站搜一下辗转相除法相关视频自己看一下。

---

完。