最大公约数的计算。从键盘接受两个整数，编写程序求出这两个整数的最大公约数和最小公倍数。（不使用Python提供的函数

）解法一：暴力枚举

最简单的方法是暴力枚举，从小到大枚举两个数的所有因数，找到最大的公共因数。时间复杂度为 $O(\min(a,b))$。

代码实现：

a = int(input("请输入第一个整数："))
b = int(input("请输入第二个整数："))

# 求最大公约数
gcd = 1
for i in range(1, min(a,b)+1):
if a % i == 0 and b % i == 0:
gcd = i

# 求最小公倍数
lcm = a * b // gcd

print("最大公约数为：", gcd)
print("最小公倍数为：", lcm)

解法二：辗转相除法

辗转相除法，也叫欧几里得算法，是求最大公约数的一种常用方法，其基本思想是用较大数除以较小数，再用余数去除除数，直到余数为0为止。此时，除数即为最大公约数。

时间复杂度为 $O(\log\min(a,b))$。

代码实现：

a = int(input("请输入第一个整数："))
b = int(input("请输入第二个整数："))

# 求最大公约数
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)

gcd = gcd(a, b)

# 求最小公倍数
lcm = a * b // gcd

print("最大公约数为：", gcd)
print("最小公倍数为：", lcm)