试编写程序,使用穷举法计算两个给定正整数的最大公约数。
时间: 2024-05-09 08:20:39 浏览: 105
C语言求最大公约数和最小公倍数算法总结
5星 · 资源好评率100%
以下是Python实现:
```python
def gcd(a, b):
"""
使用穷举法计算a和b的最大公约数
"""
# 从小到大枚举可能的公约数
for i in range(1, min(a, b) + 1):
# 如果i能同时整除a和b,则更新最大公约数
if a % i == 0 and b % i == 0:
gcd = i
return gcd
# 测试
print(gcd(12, 18)) # 输出6
print(gcd(17, 23)) # 输出1
print(gcd(60, 96)) # 输出12
```
该程序从1到min(a, b)枚举可能的公约数,如果i能同时整除a和b,则更新最大公约数。最终返回的就是最大公约数。
阅读全文