【算法积累】辗转相除法,python实现两种
- 辗转相除法(又称欧几里得算法)
- 减法(不常用)
- 代码实现
- 执行结果
- 辗转相除法
- 代码实现
- 执行结果
辗转相除法(又称欧几里得算法)
又称欧几里得算法,是一种用于求两个整数最大公约数的算法。
在辗转相除法中分为使用除法运算和使用减法运算两种方法。
减法(不常用)
代码实现
a = int(input("第一个数字:"))
b = int(input("第二个数字:"))while a!=b: # a不等于b 比如(a=42,b=12)if a > b: # 判断a>b a=a-b # a=30 此时 a还是>b 一直减到a=6elif b>a:b=b-a # 现在b>a b=12-6 =6# else不用写了,此时a=b了 跳出循环了# 上面的数字反过来也一样print("a和b的最大公约数:" ,a) # a和b相等了,输出谁都行
执行结果
C:\Users\Administrator>python xianyujiang.py
第一个数字:42
第二个数字:12
a和b的最大公约数: 6C:\Users\Administrator>python xianyujiang.py
第一个数字:22
第二个数字:42
a和b的最大公约数: 2C:\Users\Administrator>python caishuzi.py
第一个数字:4141241
第二个数字:4235235
a和b的最大公约数: 1C:\Users\Administrator>python caishuzi.py
第一个数字:3241512
第二个数字:5213152
a和b的最大公约数: 8C:\Users\Administrator>python xianyujiang.py
第一个数字:24
第二个数字:24
a和b的最大公约数: 24
辗转相除法
辗转相除法的基本思想是:用较大的数除以较小的数,然后用除数与余数再做同样的运算,直到余数为0为止,此时的除数就是两个数的最大公约数。
辗转相除法的步骤如下:
-
如果一个数能被另一个数整除,那么它们的最大公约数就是被除数。
-
如果一个数不能被另一个数整除,那么用被除数除以除数,得到的商就是新的被除数,余数就是新的除数。
-
重复上述步骤,直到余数为0,此时的除数就是最大公约数。
代码实现
a = int(input("第一个数字:"))
b = int(input("第二个数字:"))
m = max(a, b) #
n = min(a, b)
r = m % n
while r != 0:m = nn = rr = m % n
print(num1, "和", num2, "的最大公约数为", n)
执行结果
C:\Users\Administrator>python xianyujiang.py
第一个数字:20
第二个数字:40
20 和 40 的最大公约数为 20C:\Users\Administrator>python xianyujiang.py
第一个数字:12
第二个数字:42
12 和 42 的最大公约数为 6