【C语言】求两个数的最大公约数和最小公倍数（极简代码版）

题目:

7-1最大公约数和最小公倍数

本题要求两个给定正整数的最大公约数和最小公倍数。

输入格式:
输入在一行中给出两个正整数M和N (≤1000)。

输出格式:
在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。

输入样例:
511 292
输出样例:
73 2044
如图：

​编辑

代码如下：

int main()

{

    int a,b,i;

    scanf("%d %d",&a,&b);

for(i=1;(a * i) % b != 0;i++);

    printf("%d %d",b/i,a*i);




    return 0;

}

提交结果如图：

该程序的设计思路是先借助第5行代码求出a和b的最小公倍数a*i，而后借助a*b=最大公因数*最小公倍数的特性，直接用b/i求出最小公因数。

最大公约数和最小公倍数是整数数学中的两个重要概念，它们常用于分数的简化、整数的分解和解决某些数学问题。

最大公约数（Greatest Common Divisor, GCD）

定义：
两个或多个整数的最大公约数是能够同时整除这些整数的最高的正整数。

例如：

• 对于整数 18 和 24，我们需要找出它们的公约数。18 的约数是 1, 2, 3, 6, 9, 18；24 的约数是 1, 2, 3, 4, 6, 8, 12, 24。它们的公约数是 1, 2, 3, 6，其中最大的是 6。因此，18 和 24 的最大公约数是 6。

计算方法：

1. 列举法：列出所有约数，找出其中的最大值。
2. 辗转相除法：如果 a 和 b 是两个非负整数，可以通过反复取余的方式求得 gcd(a, b)。步骤如下：
   • 计算 a ÷ b，得到余数 r。
   • 令 a = b，b = r，重复这个过程，直到 r = 0，此时 b 就是最大公约数。

最小公倍数（Least Common Multiple, LCM）

定义：
两个或多个整数的最小公倍数是能被这些整数整除的最小的正整数。

例如：

• 对于整数 18 和 24，我们要找出它们的最小公倍数。18 和 24 的倍数分别是：
  • 18 的倍数：18, 36, 54, 72, 90, ...
  • 24 的倍数：24, 48, 72, 96, ...
  这两个序列中最小的共同值是 72，因此，18 和 24 的最小公倍数是 72。

计算方法：

1. 列举法：列出所有倍数，找出最小的共同倍数。
2. 使用公式：对于任意两个正整数 a 和 b，最小公倍数与最大公约数的关系是：
   LCM(𝑎,𝑏)=∣𝑎×𝑏∣GCD(𝑎,𝑏)LCM(a,b)=GCD(a,b)∣a×b∣​

​