python给定两个整数,返回最小公倍数
时间: 2023-03-20 19:00:57 浏览: 143
可以使用Python的math库中的gcd函数来求出两个整数的最大公约数,然后使用公式:两个数的乘积等于它们的最大公约数和最小公倍数的积,求出最小公倍数。代码示例:
```python
import math
def lcm(a, b):
return a*b // math.gcd(a, b)
```
其中,math.gcd(a, b)返回a和b的最大公约数,//表示整除运算符,即取整后的除法。
相关问题
输入两个正整数 m和n,求解并输出给定两个整数的最小公倍数
算法一:暴力枚举法
最简单的方法是从较大的数开始逐个判断是否同时被两个数整除,找到最小的能被整除的数即为它们的最小公倍数。但是这种方法的时间复杂度为O(mn),当m和n很大时,计算量会非常大。
算法二:辗转相除法
由于最小公倍数等于两数之积除以它们的最大公约数,所以可以先求出它们的最大公约数,然后用它们的乘积除以最大公约数即可得到最小公倍数。而求最大公约数的一个常用方法是辗转相除法,即不断用较小数去除较大数,直到余数为零为止,此时较大数就是最大公约数。
算法三:质因数分解法
将两个数分别分解质因数,然后将它们的公共因子乘起来。如果一个质数在两个数中出现的次数不同,则需要取两数中出现该质数最多的次数。例如,24和30的最小公倍数为2^3 * 3^1 * 5^1 = 120,其中2出现了3次,3和5分别出现了1次。
下面是辗转相除法的Python代码实现:
``` python
def gcd(m, n):
if n == 0:
return m
else:
return gcd(n, m % n)
m = int(input("请输入第一个正整数:"))
n = int(input("请输入第二个正整数:"))
lcm = m * n // gcd(m, n)
print("最小公倍数为:", lcm)
```
输入:
```
请输入第一个正整数:12
请输入第二个正整数:18
```
输出:
```
最小公倍数为: 36
```
python代码给定两个整数,求最大公约数和最小公倍数
可以使用辗转相除法(欧几里得算法)来求解最大公约数,同时利用最大公约数求得最小公倍数。
以下是Python代码实现:
```python
# 辗转相除法求最大公约数
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 求最小公倍数
def lcm(a, b):
return a * b // gcd(a, b)
# 示例
a = 24
b = 36
print("最大公约数:", gcd(a, b))
print("最小公倍数:", lcm(a, b))
```
输出:
```
最大公约数: 12
最小公倍数: 72
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)