Python中最大公约数的代码
a和b的最大公约数（GCD）是将它们两者相除的最大数。
一种find两个数的GCD的方法是Euclidalgorithm，它基于观察到如果r是a除以b的余数，则gcd(a, b) = gcd(b, r) 。 作为基本情况，我们可以使用gcd(a, 0) = a 。
编写一个名为gcd的函数，它需要参数a和b并返回它们的最大公约数。
这是在标准的图书馆 。
>>> from fractions import gcd >>> gcd(20,8) 4
Python 2.7中的inspect模块的源代码：
>>> print inspect.getsource(gcd) def gcd(a, b): """Calculate the Greatest Common Divisor of a and b. Unless b==0, the result will have the same sign as b (so that when b is divided by it, the result comes out positive). """ while b: a, b = b, a%b return a
从Python 3.5开始， gcd 在math模块中 ; fractions的一个被弃用。 此外， inspect.getsource不再返回任何方法的解释性源代码。
与mn的algorithm可以运行非常长。
这一个performance好得多：
def gcd(x, y): while y != 0: (x, y) = (y, x % y) return x
这个版本的代码利用Euclid的algorithm来寻找GCD。
def gcdIter(a, b): if b == 0: return a else: return gcdIter(b, a % b)
gcd = lambda m,n: m if not n else gcd(n,m%n)
def gcd(m,n): return n if (mn) == 0 else gcd(abs(mn), min(m, n))
def gcd(a,b): if b > a: return gcd(b,a) r = a%b if r == 0: return b return gcd(r,b)
我认为另一种方法是使用recursion。 这是我的代码：
def gcd(a, b): if a > b: c = a - b gcd(b, c) elif a < b: c = b - a gcd(a, c) else: return a
对于a>b ：
def gcd(a, b): if(a<b): a,b=b,a while(b!=0): r,b=b,a%r a=r return a
对于a>b或a<b ：
def gcd(a, b): t = min(a, b) # Keep looping until t divides both a & b evenly while a % t != 0 or b % t != 0: t -= 1 return t
a=int(raw_input('1st no \n')) b=int(raw_input('2nd no \n')) def gcd(m,n): z=abs(mn) if (mn)==0: return n else: return gcd(z,min(m,n)) print gcd(a,b)
基于欧几里得algorithm的另一种方法。
def gcdRecur(a, b): ''' a, b: positive integers returns: a positive integer, the greatest common divisor of a & b. ''' # Base case is when b = 0 if b == 0: return a # Recursive case return gcdRecur(b, a % b)
此代码根据＃用户给出的select计算两个以上数字的gcd，这里用户给出数字
numbers = []; count = input ("HOW MANY NUMBERS YOU WANT TO CALCULATE GCD?\n") for i in range(0, count): number = input("ENTER THE NUMBER : \n") numbers.append(number) numbers_sorted = sorted(numbers) print 'NUMBERS SORTED IN INCREASING ORDER\n',numbers_sorted gcd = numbers_sorted[0] for i in range(1, count): divisor = gcd dividend = numbers_sorted[i] remainder = dividend % divisor if remainder == 0 : gcd = divisor else : while not remainder == 0 : dividend_one = divisor divisor_one = remainder remainder = dividend_one % divisor_one gcd = divisor_one print 'GCD OF ' ,count,'NUMBERS IS \n', gcd
在pythonrecursion：
def gcd(a, b): if a%b == 0: return b return gcd(b, a%b)
价值交换对我来说效果不好。 所以我只是设置了一个镜像的情况下input的数字是<b OR a> b：
def gcd(a, b): if a > b: r = a % b if r == 0: return b else: return gcd(b, r) if a < b: r = b % a if r == 0: return a else: return gcd(a, r) print gcd(18, 2)
#This program will find the hcf of a given list of numbers. A = [65, 20, 100, 85, 125] #creates and initializes the list of numbers def greatest_common_divisor(_A): iterator = 1 factor = 1 a_length = len(_A) smallest = 99999 #get the smallest number for number in _A: #iterate through array if number < smallest: #if current not the smallest number smallest = number #set to highest while iterator <= smallest: #iterate from 1 ... smallest number for index in range(0, a_length): #loop through array if _A[index] % iterator != 0: #if the element is not equally divisible by 0 break #stop and go to next element if index == (a_length - 1): #if we reach the last element of array factor = iterator #it means that all of them are divisibe by 0 iterator += 1 #let's increment to check if array divisible by next iterator #print the factor print factor print "The highest common factor of: ", for element in A: print element, print " is: ",
greatest_common_devisor（A）
