python 最大公约数

在Python中，可以使用不同的方法来求解两个数的最大公约数。引用中的方法是列举法，即从两个数中较小的数开始，逐个列举可能的公约数，并找出最大的公约数。代码示例如下：
a=int(input("please input the first number："))
b=int(input("please input the second number："))
p,q=min(a,b),max(a,b)
lst=[]
for i in range(1,p+1):
if p%i==0 and q%i==0:
lst.append(i)
gcd=max(lst)
print(f"{a}和{b}的最大公约数为{gcd}")

另一种方法是累乘法，即逐步找出两个数的所有公约数，再将这些公约数累乘起来得到最大公约数。引用中的代码示例如下：
a=int(input("please input the first number："))
b=int(input("please input the second number："))
m,n=a,b
t=1
for i in range(2,min(a,b)):
while (a%i==0 and b%i==0):
t*=i
a/=i
b/=i
print(f"{m},{n}的最大公约数为：{t}")

另外，还有一种方法是更相减损术，即不断用较大数减去较小数，直到两个数相等或相差为1，此时的两个数即为最大公约数。这种方法在《九章算术》中提到。引用中的算法描述如下。

根据以上方法，你可以选择一种适合你的方式来求解Python中的最大公约数。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [Python求最大公约数的五种常见方法](https://blog.csdn.net/m0_69265664/article/details/125708828)[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: 100%"]
[ .reference_list ]