Python擴充套件歐幾里德演算法程式

在本文中，我們將瞭解下面給出的問題陳述的解決方案。

問題陳述 − 給定兩個數，我們需要計算這兩個數的最大公因數並顯示它們。

兩個數的最大公因數（Greatest Common Divisor）是可以整除這兩個數的最大值。這裡我們遵循歐幾里得方法來計算最大公因數，即重複除以這些數並且在餘數為零時停止。這裡我們根據遞迴中獲得的先前值擴充套件演算法。

現在讓我們在下面的實現中觀察解決方案 −

示例

# extended Euclidean Algorithm
def gcdExtended(a, b, x, y):
   # Base Case
   if a == 0 :
      x = 0
      y = 1
      return b
   x1 = 1
   y1 = 1 # storing the result
   gcd = gcdExtended(b%a, a, x1, y1)
   # Update x and y with previous calculated values
   x = y1 - (b/a) * x1
   y = x1
   return gcd
x = 1
y = 1
a = 11
b = 15
g = gcdExtended(a, b, x, y)
print("gcd of ", a , "&" , b, " is = ", g)