请求提供两个正整数,计算它们的最大公约数(GCD)和最小公倍数(LCM),该如何操作?
时间: 2024-10-08 13:04:06 浏览: 9
为了计算两个正整数的最大公约数(GCD)和最小公倍数(LCM),你可以采用以下步骤:
1. **最大公约数(GCD)**:
- 使用欧几里得算法(Euclidean algorithm),也称为辗转相除法。这个算法基于这样一个事实:对于任何两个非零整数a和b,它们的最大公约数等于较小的那个数和两数相除余数的最大公约数。如果a能整除b,则GCD(a, b) = b;否则GCD(a, b) = GCD(b, a mod b)。
2. **最小公倍数(LCM)**:
- LCM通常通过GCD来计算,因为有公式Lcm(a, b) = |a * b| / Gcd(a, b)。这意味着两个数的乘积除以它们的最大公约数就是它们的最小公倍数。
如果你需要编写一段程序实现这个功能,可以用循环或递归的方式来计算GCD,然后用上述公式求出LCM。这里是一个简单的Python示例:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
num1 = int(input("请输入第一个正整数:"))
num2 = int(input("请输入第二个正整数:"))
gcd_result = gcd(num1, num2)
lcm_result = lcm(num1, num2)
print(f"最大公约数(GCD):{gcd_result}")
print(f"最小公倍数(LCM):{lcm_result}")