Python|两种不同方法求最大公约数GCD（Greatest Common Divisor）（Python） Python|算法

【Python|两种不同方法求最大公约数GCD（Greatest Common Divisor）（Python）】
两种不同方法求最大公约数（Python）

方法一：从1开始依次查找

Python3实现
方法二：欧几里得算法（辗转相除法）
Python3代码实现

方法一：从1开始依次查找

# pseudocode gcd = 1 int k = 2 #Possible gcd while k <= n1 and k <= n2: if n1 % k == 0 and n2 % k == 0: gcd = k k += 1

Python3实现

#Finding the Greatest Common Divisorn1 = eval(input("Enter first number: ")) n2 = eval(input("Enter second number: "))gcd = 1 k = 2 while k <= n1 and k <= n2: if n1 % k == 0 and n2 % k == 0: gcd = k k += 1print("The greatest common divisor for", n1, "and ", n2, "is", gcd) input("press Enter: ")

方法二：欧几里得算法（辗转相除法）原理解释如连接：英文算法解释

通俗易懂算法解释
Python3代码实现

#Finding the Greatest Common Divisor Euclid's Algorithmn1 = eval(input("Enter first number: ")) n2 = eval(input("Enter second number: "))number1, number2 = n1, n2 if n1 < n2: n1, n2 = n2, n1gcd = 1 while n2 != 0: gcd = n1 % n2 n1 = n2 n2 = gcd print("gcd: n1: n2 :", gcd, n1, n2) gcd = n1print("The greatest common divisor for", number1, "and ", number2, "is", gcd) input("press Enter: ")