【算法积累】辗转相除法

【算法积累】辗转相除法，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=6
    elif 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的最大公约数： 6

C:\Users\Administrator>python xianyujiang.py
第一个数字：22
第二个数字：42
a和b的最大公约数： 2

C:\Users\Administrator>python caishuzi.py
第一个数字：4141241
第二个数字：4235235
a和b的最大公约数： 1

C:\Users\Administrator>python caishuzi.py
第一个数字：3241512
第二个数字：5213152
a和b的最大公约数： 8

C:\Users\Administrator>python xianyujiang.py
第一个数字：24
第二个数字：24
a和b的最大公约数： 24

辗转相除法

辗转相除法的步骤如下：

1. 如果一个数能被另一个数整除，那么它们的最大公约数就是被除数。

2. 如果一个数不能被另一个数整除，那么用被除数除以除数，得到的商就是新的被除数，余数就是新的除数。

3. 重复上述步骤，直到余数为0，此时的除数就是最大公约数。

代码实现

a = int(input("第一个数字："))
b = int(input("第二个数字："))
m = max(a, b)            # 
n = min(a, b)
r = m % n
while r != 0:
    m = n
    n = r
    r = m % n
print(num1, "和", num2, "的最大公约数为", n)

执行结果

C:\Users\Administrator>python xianyujiang.py
第一个数字：20
第二个数字：40
20 和 40 的最大公约数为 20

C:\Users\Administrator>python xianyujiang.py
第一个数字：12
第二个数字：42
12 和 42 的最大公约数为 6