【基础入门题】2021.12.09
给定两个正整数数，求这两个数的最大公约数。
编程语言：包括但不限于Python
题目来源：派森特给站每日刷题频道
————————————————
方法一：for循环
def GCD(m, n): gcd = 1 # 此行可以省略 for i in range(1,min(m, n)+1): if m%i==0 and n%i==0: gcd = i return gcd print(GCD(81,3)) print(GCD(81,15)) print(GCD(81,54))
方法二：while循环
def GCD(m, n): while m!=n: if m>n: m -= n else: n -= m return m print(GCD(81,3)) print(GCD(81,15)) print(GCD(81,54))
方法三：递归法
def GCD(m, n): if n==0: return m return GCD(n, m%n) print(GCD(81,3)) print(GCD(81,15)) print(GCD(81,54))
方法四：辗转相除法
def GCD(m, n): while n!=0: m, n = n, m%n return m print(GCD(81,3)) print(GCD(81,15)) print(GCD(81,54))
方法五：递减法
def GCD(m, n): gcd = min(m, n) while m%gcd or n%gcd: gcd -= 1 return gcd print(GCD(81,3)) print(GCD(81,15)) print(GCD(81,54))
方法六：库函数math.gcd
from math import gcd print(gcd(81,3)) print(gcd(81,15)) print(gcd(81,54))
或者：直接用 __import__('math').gcd
1. __import__('math').gcd(81,3) 2. __import__('math').gcd(81,15) 3. __import__('math').gcd(81,54)
方法七：约分法，库函数fractions.Fraction()
def GCD(m, n): from fractions import Fraction return m//Fraction(m, n).numerator #取分子 #return n//Fraction(m, n).denominator #或取分母 print(GCD(81,3)) print(GCD(81,15)) print(GCD(81,54))
以上方法的答案均为 3,3,27。
