用辗转相除法求两个正整数的最大公约数
时间: 2023-12-25 10:03:27 浏览: 31
设两个正整数为a和b(a>b)。
1. 用a除以b,得到余数r1,即a=b*q1+r1(q1为商,r1为余数)。
2. 如果r1等于0,则最大公约数为b,算法结束。
3. 如果r1不等于0,则用b除以r1,得到余数r2,即b=r1*q2+r2。
4. 如果r2等于0,则最大公约数为r1,算法结束。
5. 如果r2不等于0,则继续用r1除以r2,得到余数r3,即r1=r2*q3+r3。
6. 以此类推,直到余数为0为止。最后一个非零余数就是最大公约数。
举个例子:
求36和24的最大公约数。
36÷24=1···12,余数为12
24÷12=2···0,余数为0
因此,最大公约数为12。
相关问题
用辗转相除法求两个正整数的最大公约数。
辗转相除法(也叫欧几里得算法)是一种求最大公约数的算法。它的基本思想是用较大数除以较小数,再用除数除以余数,直到余数是零。最后除数就是最大公约数。
示例:
求最大公约数(24,18)
24÷18 = 1......6
18÷6 = 3
6÷3 = 2
所以最大公约数(24,18) = 6.
辗转相除法求两个正整数最大公约数和最小公倍数的代码python
以下是求两个正整数最大公约数和最小公倍数的辗转相除法代码:
```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 为止。此时,较小的数即为最大公约数,较大的数与最大公约数的乘积即为最小公倍数。