输入两个正整数求它们的最小公倍数
时间: 2023-12-09 07:50:55 浏览: 35
求两个正整数的最小公倍数可以通过先求它们的最大公约数,再用两数之积除以最大公约数得到。最大公约数可以用辗转相除法(又称欧几里得算法)求得,具体步骤如下:
1. 用较小数除以较大数,得到余数(0除外);
2. 用上一步得到的余数去除较小数,再得到余数(若余数为0,则最大公约数为除数,否则继续执行下一步);
3. 重复上一步,直到余数为0,此时除数即为最大公约数。
最小公倍数等于两数之积除以它们的最大公约数。
以下是 Python 代码实现:
```python
def gcd(a, b):
# 求a和b的最大公约数
while b:
a, b = b, a % b
return a
def lcm(a, b):
# 求a和b的最小公倍数
return a * b // gcd(a, b)
# 读入两个正整数
a = int(input("请输入第一个正整数:"))
b = int(input("请输入第二个正整数:"))
# 输出它们的最小公倍数
print("它们的最小公倍数是:", lcm(a, b))
```
示例输出:
```
请输入第一个正整数:12
请输入第二个正整数:18
它们的最小公倍数是: 36
```
相关问题
输入两个正整数,求最小公倍数
可以使用以下方法求解两个正整数的最小公倍数:
1. 分解两个数的质因数;
2. 将这两个数中所有质因数的指数的最大值相乘。
例如,求 12 和 18 的最小公倍数:
1. 12 = 2^2 × 3,18 = 2 × 3^2;
2. 两个数的所有质因数为 2、3,它们的指数的最大值分别为 2 和 2,因此它们的最小公倍数为 2^2 × 3^2 = 36。
因此,12 和 18 的最小公倍数为 36。
输入两个正整数求最大公约数最小公倍数
最大公约数可以使用辗转相除法或欧几里得算法求解,最小公倍数可以通过最大公约数求解。
辗转相除法:
设两个正整数为a和b,且a>b,用a除以b,得到余数r,若r为,则b即为最大公约数;若r不为,则用b除以r,得到余数r1,若r1为,则r即为最大公约数;若r1不为,则继续用r除以r1,直到余数为为止。
最大公约数:两个正整数a和b的最大公约数为gcd(a,b)。
最小公倍数:两个正整数a和b的最小公倍数为lcm(a,b) = a*b/gcd(a,b)。
例如,输入两个正整数10和15,先求最大公约数,使用辗转相除法,得到:
10÷15=...10
15÷10=1...5
10÷5=2...
因此,gcd(10,15)=5。
再求最小公倍数,使用公式lcm(10,15) = 10*15/5 = 30。
因此,10和15的最大公约数为5,最小公倍数为30。