首页c语言用辗转相除法求最小公倍数和最大公因数

c语言用辗转相除法求最小公倍数和最大公因数

时间: 2024-12-18 13:19:15 浏览: 65

在C语言中，可以使用欧几里得算法（也称为辗转相除法或更相减损术）来计算两个整数的最大公约数（Greatest Common Divisor, GCD）以及它们的最小公倍数（Least Common Multiple, LCM）。以下是基本的步骤： **计算最大公约数（GCD）**： 1. 对于两个正整数a和b（假设a >= b），如果b等于0，则a就是它们的GCD；否则，GCD(a, b) = GCD(b, a % b)。 2. 这是因为每次取余操作（a % b），都会使得较大的数变成较小数的倍数，而原来较小的数变成了两者的余数。这个过程会一直持续到余数为0。 **计算最小公倍数（LCM）**： 1. 利用公式 LCM(a, b) = |a * b| / GCD(a, b)，其中“| |”表示绝对值，因为当两个数互质时（即GCD为1），它们的乘积就是最小公倍数。 2. 先计算出a和b的GCD，然后用两数之积去除以这个GCD即可得到LCM。下面是一个简单的C语言函数示例，用于计算GCD和LCM： ```c #include <stdio.h> // 辗转相除法计算GCD int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } // 计算LCM int lcm(int a, int b) { return (a * b) / gcd(a, b); } int main() { int num1, num2; printf("Enter two numbers: "); scanf("%d %d", &num1, &num2); int result_gcd = gcd(num1, num2); int result_lcm = lcm(num1, num2); printf("GCD of %d and %d is: %d\n", num1, num2, result_gcd); printf("LCM of %d and %d is: %d\n", num1, num2, result_lcm); return 0; } ```

阅读全文