使用Python求解最大公约数的实现方法
1. 欧几里德算法 欧几里德算法又称辗转相除法, 用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理: 证明: 欧几里德的Python语言描述为: def gcd(a,b): if a < b: a,b = b,a while b != 0: temp = a % b a = b b = temp return a 2. Stein算法 def gcd_Stein(a,b): if a < b: a,a if (0 == b): return a if a % 2 == 0 and b % 2 == 0: return 2 * gcd_Stein(a/2,b/2) if a % 2 == 0: return gcd_Stein(a / 2,b) if b % 2 == 0: return gcd_Stein(a,b / 2) return gcd_Stein((a + b) / 2,(a - b) / 2) 3. 一般求解实现 核心代码很简单: def gcd(a,b): if b == 0:return a return gcd(b,a % b) 附上一个用Python实现求最大公约数同时判断是否是素数的一般方法: #!/usr/bin/env python def showMaxFactor(num): count = num / 2 while count > 1: if num % count == 0: print 'largest factor of %d is %d' % (num,count) break #break跳出时会跳出下面的else语句 count -= 1 else: print num,"is prime" for eachNum in range(10,21): showMaxFactor(eachNum) 输出如下: largest factor of 10 is 5 11 is prime largest factor of 12 is 6 13 is prime largest factor of 14 is 7 largest factor of 15 is 5 largest factor of 16 is 8 17 is prime largest factor of 18 is 9 19 is prime largest factor of 20 is 10 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |