辗转相除法求两个正整数最大公约数和最小公倍数的代码python
时间: 2023-11-17 08:04:36 浏览: 44
以下是求两个正整数最大公约数和最小公倍数的辗转相除法代码:
```python
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
```
其中,`gcd` 函数用于求最大公约数,`lcm` 函数用于求最小公倍数。辗转相除法的思路是用较小的数去除较大的数,然后用余数去除较小的数,一直重复这个过程,直到余数为 0 为止。此时,较小的数即为最大公约数,较大的数与最大公约数的乘积即为最小公倍数。
相关问题
输入两个正整数,利用辗转相除法求最大公约数和最小公倍数
辗转相除法,也叫欧几里得算法,是求最大公约数的一种方法。具体步骤如下:
1. 输入两个正整数a和b(a>b)。
2. 用a除以b,得到商q和余数r。
3. 若r=0,则b即为最大公约数。
4. 若r≠0,则用b除以r,得到商q1和余数r1。
5. 若r1=0,则r即为最大公约数。
6. 若r1≠0,则继续用r除以r1,得到商q2和余数r2。
7. 重复上述步骤,直到余数为0为止。
最小公倍数可以通过最大公约数求得,公式为:a*b/最大公约数(a,b)。
具体代码如下:
```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 = int(input("请输入第一个正整数:"))
b = int(input("请输入第二个正整数:"))
print("最大公约数为:", gcd(a, b))
print("最小公倍数为:", lcm(a, b))
```
以下程序用辗转相除法求出两个正整数的最大公约数和最小公倍数
```python
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
def lcm(a, b):
return a * b // gcd(a, b)
a = int(input())
b = int(input())
print("最大公约数为:", gcd(a, b))
print("最小公倍数为:", lcm(a, b))
```
其中,`gcd`函数用于求最大公约数,`lcm`函数用于求最小公倍数。程序输入两个正整数`a`和`b`,输出它们的最大公约数和最小公倍数。