def greatest_common_divisor_1(self, num1, num2):    '''    數(shù)值計(jì)算尋找最大公約數(shù)，給定兩個(gè)整數(shù)，計(jì)算其最大公約數(shù)，時(shí)間復(fù)雜度為 o(min(num1,num2))，取余運(yùn)算復(fù)雜度高    '''    gbc = 1    for i in xrange(2, min(num1, num2)+1):      if num2 % i == 0 and num1 % i == 0:        gbc = i    return gbc  def greatest_common_divisor_2(self, num1, num2):    '''    輾轉(zhuǎn)相減法，時(shí)間復(fù)雜度最差為 o(min(num1,num2))，一般情況下都比這個(gè)要好。相減運(yùn)算要比除法方便很多    '''    while num1 != num2:      if num1 > num2:        num1 = num1 - num2      else:        num2 = num2 - num1    return num1  def greatest_common_divisor_3(self, num1, num2):    '''    求余數(shù)法，取模運(yùn)算比較麻煩，時(shí)間復(fù)雜度低 o(log max(num1, num2))    '''    while num1 != num2:      if num1 > num2:        if num1 % num2 == 0:          return num2        num1 = num1 % num2      else:        if num2 % num1 == 0:          return num1        num2 = num2 % num1    return num1  def greatest_common_divisor(self, num1, num2):    '''    求兩個(gè)數(shù)的最大公約數(shù)    綜合取余法和輾轉(zhuǎn)相減法，既能得到較好的時(shí)間復(fù)雜度，又能避免取余運(yùn)算，時(shí)間復(fù)雜度穩(wěn)定 o(log max(num1,num2))    如果取兩個(gè)非常大的數(shù)的話，前面的方法很容易爆棧、取余困難等等，但是該方法沒(méi)有問(wèn)題    a = 999999342353200    b = 777774234    print greatest_common_divisor(a, b)    '''    factor = 1    if num1 < num2:      return greatest_common_divisor_1(num2, num1)    while num1 != num2:      if num1 & 1 is False and num2 & 1 is False: # 均為偶數(shù)        num1 = num1 >> 1        num2 = num2 >> 2        factor *= 2      elif num1 & 1 is False and num2 & 1 is True:        num1 = num1 >> 1      elif num1 & 1 is True and num2 & 1 is False:        num2 = num2 >> 1      else:        if num1 > num2:          num1 = num1 - num2        else:          num2 = num2 - num1    return factor*num1