春招学考社团_python专题_zt1_最大公约数.py
- 2026-02-28 01:15:48
春招学考社团_python专题_zt1_最大公约数.py
专题知识点：最大公约数
最大公约数（GCD）概念：指两个或多个整数共有约数中最大的一个
例子1：辗转相除法（欧几里得算法）： 效率最高的经典方法
def gcd_euclidean(a, b):# 第一步：处理输入，确保计算的是非负整数（取绝对值）a = abs(a)b = abs(b)# 核心逻辑：当余数不为0时，持续循环计算while b != 0:# 计算a除以b的余数remainder = a % b# 更新a为原来的b，b为上一步得到的余数a = bb = remainder# 当余数b为0时，此时的a就是两个数的最大公约数return a# 测试辗转相除法num1 = 48num2 = 18result = gcd_euclidean(num1, num2)print(f"{num1}和{num2}的最大公约数是：{result}")
输出：48和18的最大公约数是：6
#例子2：暴力破解(枚举法)：思路简单但效率较低
def gcd_enumeration(a, b):# 第一步：处理输入，确保计算的是非负整数（取绝对值）a = abs(a)b = abs(b)# 找到两个数中的较小值，因为最大公约数不可能超过较小的数min_num = min(a, b)# 从较小值开始向下枚举（从大到小找，找到第一个符合条件的就是最大的）for i in range(min_num, 0, -1):# 判断当前数i是否能同时整除a和bif a % i == 0 and b % i == 0:# 找到则立即返回，保证是最大的公约数return i# 保底返回1（所有整数都能被1整除）return 1# 测试枚举法num1 = 48num2 = 18result = gcd_enumeration(num1, num2)print(f"{num1}和{num2}的最大公约数是：{result}")
输出：48和18的最大公约数是：6
例子3：使用Python内置库的math.gcd函数：实际开发推荐使用
import math # 导入Python内置的数学库# 测试内置函数num1 = 48num2 = 18result = math.gcd(num1, num2) # 直接调用内置函数计算最大公约数print(f"{num1}和{num2}的最大公约数是：{result}")
输出：48和18的最大公约数是：6
本文来自网友投稿或网络内容，如有侵犯您的权益请联系我们删除，联系邮箱：wyl860211@qq.com 。
