题目：输入两个正整数m和n，求其最大公约数和最小公倍数。
方法1: 辗转相除法（欧几里德算法）求最大公约数
def gcd_euclidean(m, n):
while n:
m, n = n, m % n
return m
m = 36
n = 48
gcd_result = gcd_euclidean(m, n)
print("GCD:", gcd_result)
# 计算最小公倍数公式: LCM = m * n / GCD
lcm_result = (m * n) // gcd_result
print("LCM:", lcm_result)
思路：
- 使用辗转相除法（欧几里德算法），不断地用较小数去除较大数，直到余数为0。最终的除数就是最大公约数。
优点：
- 算法简单、高效，适用于大整数。
缺点：
- 除法运算可能会引入浮点数运算误差，需要注意。
方法2: 更相减损术求最大公约数
def gcd_subtraction(m, n):
if m == n:
return m
elif m > n:
return gcd_subtraction(m - n, n)
else:
return gcd_subtraction(m, n - m)
m = 36
n = 48
gcd_result = gcd_subtraction(m, n)
print("GCD:", gcd_result)
# 计算最小公倍数公式: LCM = m * n / GCD
lcm_result = (m * n) // gcd_result
print("LCM:", lcm_result)
思路：
- 使用更相减损术，不断地用较大数减去较小数，直到两数相等。最终的相等数就是最大公约数。
优点：
- 算法简单、直观。
缺点：
- 算法的递归深度可能较大，特别是对于较大的整数。
方法3: 利用公式求最小公倍数
def lcm_formula(m, n):
# LCM = m * n / GCD
gcd_result = gcd_euclidean(m, n)
return (m * n) // gcd_result
m = 36
n = 48
gcd_result = gcd_euclidean(m, n)
print("GCD:", gcd_result)
lcm_result = lcm_formula(m, n)
print("LCM:", lcm_result)
思路：
- 利用最大公约数公式求最小公倍数。
优点：
- 可以重用最大公约数算法，简化计算。
缺点：
- 需要调用最大公约数算法。
方法总结及推荐
-
推荐方法： 方法1中的辗转相除法（欧几里德算法）是最常用且高效的方法，它能够快速求解最大公约数，并通过公式直接计算最小公倍数。
-
适用场景：
- 对于最大公约数和最小公倍数的求解，推荐使用辗转相除法（欧几里德算法）及公式计算，因为它们简单、高效，并且能够处理大整数。
- 更相减损术可以作为一种直观的方法，但可能在递归深度较大时效率不高。
