C 语言求两个数的 GCD 和 LCM 的程序

在本文中，我们将讨论使用C语言查找两个数的GCD和LCM的程序。

GCD - 最大公约数

GCD代表最大公约数。GCD是最大的正整数，因为它可以整除给定的正整数集合。GCD代表Greatest Common Divisor。

最大公约数（GCD）用于比较两个整数，它除以最大的正整数。它有几个名称，也称为最高公因子（HCF）或最大公因子（GCF）。

GCD通常用于两个数字，以便将分数简化到其最小项。互质或相对素数是指两个数字的GCD为1的数字。

查找GCD的步骤

使用以下步骤查找GCD

1. 列出正整数“m”的因子。
2. 列出组成正整数“n”的因子。
3. 找出“m”和“n”的公因子。
4. 找出m和n的公因子中最大的值。

示例

• 15的因子：1, 3, 5, 15。
• 18的因子：1, 2, 3, 6, 9和18。
• 15和18的公因子是1, 3。
• 15和18的GCD是3。

LCM - 最小公倍数

两个整数a和b的LCM是能被a和b整除的最小正整数。因此，最小的正整数是至少另外两个数的倍数。

查找LCM的步骤

使用以下步骤查找LCM：

1. 选择两个数字：称它们为num1和num2。
2. 查找最大公约数（GCD）：使用欧几里得算法等算法来确定两个数字的GCD。
3. 使用LCM公式：在获得GCD后，您可以使用以下公式确定LCM

(num1 * num2) / GCD = LCM

示例

• 列出4和6的倍数
• 4：4, 8, 12, 16, 20, 24, 28, ...
• 6：6, 12, 18, 24, 30, 36, 42, ...

最后两条陈述指出4和6的公倍数是12和24。如果我们继续下去，它们可能会有更多的公倍数。对于4和6，12是目前最小的公倍数。因此，4和6的LCM是12。

GCD和LCM之间的关系

最大公约数（GCD）是两个或多个给定数字的公因子中最大的一个。最小公倍数是两个或多个给定数字的公倍数中最小的一个。假设a和b是两个数字，则计算a和b的LCM和GCD之间关系的方程为

示例

下面是使用C语言查找两个数gcd和lcm的程序。

输出

Enter the first number: 15
Enter the second number: 18
GCD of 15 and 18 is  = 3
LCM of 15 and 18 is  = 90

说明

1. #include<stdio.h>：它包含程序中的输入/输出库。
2. main函数开头的int语句。
3. 位于main函数内部：
   • 声明整数变量 number_1, number_2（输入数字）、i（循环变量）、gcd（最大公约数）和lcm（最小公倍数）。通过语句int number_1, number_2 gcd lcm。
   • 使用语法printf("Enter the first number: ");显示一条消息，要求用户输入第一个数字。
   • 使用函数scanf("%d", &number_1)从用户读取一个整数并将其赋给number_1。
   • 使用语法printf("Enter the second number: ");显示一条消息，要求用户输入第二个数字。
   • 使用函数scanf("%d", &number_2)读取用户输入的下一个整数并将其赋给number_2。
   • 调用一个for循环，该循环从1开始，到两个输入数字（number_1和number_2）中较小的那个结束。该循环为for(i=1; i<=number_1 &&i<=number_2; i++)。
   • for循环包含
     1. 检查当前值i是否同时是number_1和number_2的因子，即number_1%i==0和number_2%i==0。
     2. 如果条件为true，则更新gcd变量为当前值i。使用之前确定的GCD计算LCM。
   • 使用公式lcm=(number_1*number_2)/gcd，利用之前确定的GCD计算LCM。
   • printf函数显示两个输入数字的GCD，消息为"GCD of%dand%d is =%dn"。
   • 此命令打印两个输入数字的LCM：printf("LCM of%dand%d is =%dn", number_1, number_2, lcm);。
4. return 0;: 返回0表示程序已成功运行并已向操作系统报告。