最大公约数

NC22215. 最大公约数

描述

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。给你两个数，请输出他们的最大公约数。

输入描述

输入一行，包含两个正整数A,B

1 <= A,B <= 1e9

输出描述

输出一行，包含一个正整数

示例1

输入:

4 6

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

pypy3 解法, 执行用时: 131ms, 内存消耗: 48176K, 提交时间: 2021-08-12 11:43:03

import math
a,b=map(int,input().split(' '))
print(math.gcd(a, b))

Python3 解法, 执行用时: 37ms, 内存消耗: 4560K, 提交时间: 2021-12-08 20:10:03

a,b=map(int,input().split())
while b:
    a,b=b,a%b
print(a)

详情