输入两个正整数 求其最大公约数和最小公倍数
时间: 2023-11-10 19:58:35 浏览: 49
算法一:
最大公约数可以使用辗转相除法(又称欧几里得算法)来求解,具体步骤如下:
1. 用较小数除以较大数,得到余数
2. 把较大数作为下一轮的较小数,余数作为下一轮的较大数,重复上述步骤,直到余数为0
3. 最后的较大数即为最大公约数
最小公倍数可以通过最大公约数来求解,公式为两数之积除以最大公约数。
代码实现如下:
a = int(input("请输入第一个正整数:"))
b = int(input("请输入第二个正整数:"))
# 求最大公约数
x, y = max(a, b), min(a, b)
while y:
x, y = y, x % y
gcd = x
# 求最小公倍数
lcm = a * b // gcd
print("最大公约数为:", gcd)
print("最小公倍数为:", lcm)
算法二:
最大公约数可以使用质因数分解来求解,具体步骤如下:
1. 分别对两个数进行质因数分解
2. 找出两个数中共有的质因数及其次数,次数取两个数中次数的最小值
3. 把这些公共质因数相乘,得到最大公约数
最小公倍数可以通过最大公约数和两数之积来求解,公式为两数之积除以最大公约数。
代码实现如下:
a = int(input("请输入第一个正整数:"))
b = int(input("请输入第二个正整数:"))
# 求最大公约数
factors_a, factors_b = [], []
for i in range(2, a + 1):
while a % i == 0:
factors_a.append(i)
a //= i
for i in range(2, b + 1):
while b % i == 0:
factors_b.append(i)
b //= i
gcd = 1
for i in factors_a:
if i in factors_b:
gcd *= i
factors_b.remove(i)
# 求最小公倍数
lcm = a * b // gcd
print("最大公约数为:", gcd)
print("最小公倍数为:", lcm)