python四种方法求最大公约数(枚举法,辗转相除法,更相减损术,短除法)
python四种方法求最大公约数(枚举法,辗转相除法,更相减损术,短除法)
·
#枚举法
def MJFg_c_d(a,b):
big=max(a,b)
small=min(a,b)
if big % small == 0:
return small
for i in range(small//2, 1, -1):
if small % i == 0 and big % i == 0:
return i
return 1
def MJFl_c_m(a,b):
big=max(a,b)
small=min(a,b)
if big%small==0:
return big
for i in range(big,small*big+1):
if i%small==0 and i%big==0:
return i
print('(21,49)枚举法:最大公约数',MJFg_c_d(21,49),'最小公倍数',MJFl_c_m(21,49))
#辗转相除法
def ZZXCFg_c_d(a,b):
big=max(a,b)
small=min(a,b)
if big%small==0:
return small
return ZZXCFg_c_d(big%small,small)
print('更相减损术(21,49)最大公约数为:',ZZXCFg_c_d(21,49))
#更相减损术
def GXHCSg_c_d(a,b):
if a==b:
return a
big = max(a, b)
small = min(a, b)
return GXHCSg_c_d(big-small,small)
print('更相减损术(21,49)最大公约数为:',GXHCSg_c_d(21,49))
#短除法
a,b=21,49
m,n=a,b # 创建两个变量存储a和b
t=1 # 创建t作为最大公约数的载体
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}")
运行结果图
更多推荐
已为社区贡献4条内容
所有评论(0)