python 辗转相除

辗转相除法是一种求两个数的最大公约数的方法，也被称为欧几里得算法。在Python中，可以使用以下代码实现辗转相除法求最大公约数：

# 输入整数
a = int(input('请输入第一个整数：'))
b = int(input('请输入第二个整数：'))

# 将b变成较小的那个数
if a < b:
    smaller = a
    a = b
    b = smaller

# 不断将gcd(a,b)的问题转化成gcd(b,a%b)的问题
while b != 0:
    r = a % b
    a = b
    b = r

print('最大公约数为：', a)

这段代码中，首先将输入的两个整数中较小的那个数放在变量b中，然后使用while循环将求最大公约数的问题转化为求a除以b的余数r，然后将a赋值给b，将r赋值给a，继续计算，直到余数为0，此时a即为最大公约数。

这段代码的原理是利用了辗转相除法的思想，即两个数的最大公约数等于其中较小的数和两数的差的最大公约数。通过不断求余数的方式，逐步缩小两个数之间的差距，直到余数为0，即找到了最大公约数。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* [小皮从零学算法（一）：辗转相除法求最大公约数算法证明及Python代码](https://blog.csdn.net/NicholeChen/article/details/108051456)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *3* [python-辗转相除法求最大公约数](https://blog.csdn.net/qq_61871289/article/details/129569262)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]