一行代码求两个数的最大公约数

[编程题]一行代码求两个数的最大公约数

热度指数：1181 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个不等于0的整数M和N，求M和N的最大公约数。

输入描述:

输入有两个整数。分别表示M, N

输出描述:

一个整数表示M, N的最大公约数

示例1

输入

6 12

输出

示例2

输入

2 3

输出

备注:

算法知识视频讲解

Python

圣诞节的安徒生

def maxCommonDivisor(m, n):
    if m == 1 or n == 1 or m == n:
        return m
    #调整m,n的顺序使得m<n
    if m > n:
        m, n = n, m
    if n % m == 0:
        return m
    for i in range(1, m):
        if m % i == 0 and n % i == 0:
            commonDivisor = i
    return commonDivisor
m, n = map(int, input().split())
print(maxCommonDivisor(m, n))

辗转相除法：

def maxCommonDivisor(m, n):
    #辗转相除法
    #调整m,n的顺序使得m<n
    if m > n:
        m, n = n, m
    if n % m == 0:
        return m
    else:
        return maxCommonDivisor(m, n%m)

m, n = map(int, input().split())
print(maxCommonDivisor(m, n))

调整m,n的顺序使用系统函数sorted，会大幅度节省运行的空间