【C语言】–输入两个正整数m和n，求其最大公约数和最小公倍数。

目录

最大公约数和最小公倍数的定义

方法一：简单暴力直接法

方法二：辗转相除法（最大公约数）

最大公约数和最小公倍数的定义

最小公倍数是指两个或多个数的公共倍数中最小的一个数。

最大公约数则是指两个或多个数的公共因数中最大的一个数。

例如，对于数3和5，它们的最小公倍数是15，最大公约数是1。

X和Y的最大公约数和最小公倍数的关系：最小公倍数=（ X * Y ）/ 最大公约数

方法一：简单暴力直接法

通过定义，可以知道：

最大公约数一定不会大于两个数之间的最小数，最大也就是两个数的最小值；最小公倍数一定大于或等于两个数的最大值。

所以，就有了简单暴力直接法的产生：

求最大公约数是把最小值赋给变量j，然后两个数再对变量j取余，判断是否能整除，不能整除变量tj就自减1，直到整除为止。
求最小公倍数是把最大值赋给变量i，然后变量i再分别对两个数取余，判断是否能整除，不能整除变量i就自加1，直到整除为止。

代码：

#define _CRT_SECURE_NO_WARNINGS 1//在VS2019中使用scanf函数需要添加#includeint main(){int a, b, i, j;int max = 0;printf("请输入两个整数：\n");scanf("%d%d", &a, &b);for (i = a;;i++){if (i % a == 0 && i % b == 0)//求最小公倍数break; //利用i++，第一个i对a和b同时取余为零的数i即为最大公约数}for (j = b;;j--){if (a % j == 0 && b % j == 0)//求最大公约数break;//利用j--，第一个a和b同时除尽的数j即为最大公约数}printf("最大公约数：%d\n最小公倍数：%d\n", j, i);return 0;}

测试结果：

方法二：辗转相除法（最大公约数）

数学原理：

X和Y的最大公约数和最小公倍数的关系：最小公倍数=（ X * Y ）/ 最大公约数

代码：

int main(){int x, y, a, b, temp, r = 0, min = 0;printf("请输入两个整数：\n");scanf("%d%d", &x, &y);if (x < y)//交换大小顺序，大数对小数取余{temp = x;x = y;y = temp;}a = x;b = y;r = a % b;while (r != 0) //辗转相除求最大公因数，b即为最后的最大公因数{a = b;b = r;r = a % b;}min =( x * y) / b; //最小公倍数printf("最大公因数：%d\n最小公倍数：%d\n", b, min);return 0;}

测试结果