Python：三种方法计算最大公约数和最小公倍数(欧几里德法、穷举法、stein算法) |
您所在的位置：网站首页 › 如何用python求两个数的最大公约数和最小值 › Python：三种方法计算最大公约数和最小公倍数(欧几里德法、穷举法、stein算法) |
|
Python：三种方法计算最大公约数和最小公倍数
1.穷举法
2.欧几里德法
3.Stein算法
题目：求取任意两个非负数(至多一个数为0)的最大公约数和最小公倍数； 参考资料：Python解决求最大公约数和最小公倍数问题 link；最小公约数（欧几里得算法&stein算法） link 1.穷举法两个非负数(至多一个数为0)的存在情况：其中一个数为0；两个数均为正数。当两个数中有一个数为0时，最大公约数为另一个非零数；当两个均为正数时，选择较小的正数(两个数的最大公约数肯定小于或等于较小的数)，从大到小进行列举，得到的公约数即为最大公约数。 最小公倍数=两数乘积/最大公约数 实现代码如下： // An highlighted block #输入参数 #最大公约数 def gcd_exhaus(a,b): if a==0 and b==0: print("请重新输入参数") #break elif min(a,b)==0: return max(a,b) elif a==b: return a else: a,b=max(a,b),min(a,b) for i in range(b,0,-1): #从大到小列举 if a%i==0 and b%i==0: return i break else: continue gcd_exhaus(8,4) #最小公倍数 def lcm_exhaus(a,b): return a*b/gcd_exhaus(a,b) lcm_exhaus(8,4) 2.欧几里德法欧几里德法也称辗转相除法，假设有两个整数a、b，且满足条件a>b，若a%b不为0，则对a、b求最大公约数等价于对b、(a%b)求最大公约数。依此类推，直至两数可以整除。 实现代码如下： // An highlighted block #最大公约数 def gcd_euclid(a,b): if a==0 and b==0: print("请重新输入参数") #break elif min(a,b)==0: return max(a,b) else: a,b=max(a,b),min(a,b) if a%b==0: return b else: return gcd_euclid(b,a%b) gcd_euclid(12,3) #最小公倍数 def lcm_euclid(a,b): return a*b/gcd_euclid(a,b) lcm_euclid(12,3) 3.Stein算法欧几里德算法是计算两个数最大公约数的传统算法，无论从理论还是从实际效率上都是很好的。但当出现大素数时，欧几里德法则存在较大的缺陷。 Stein算法: 假设 A 1 = A , B 1 = B , C 1 = 1 A_1=A,B_1=B,C_1=1 A1=A,B1=B,C1=1： for n = 1 , 2 , 3 , . . . n=1,2,3,... n |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |