03248: 最大公约数

math, http://cs101.openjudge.cn/practice/03248

给定两个正整数，求它们的最大公约数。

输入

有多组数据，每行为两个正整数，且不超过int可以表示的范围。

输出

行对应输出最大公约数。

样例输入

4 8
8 6
200 300

样例输出

4
2
100

提示

系统的测试文件中数据有很多组，因此同学们在程序里要写循环读取数据并判断是否读完文件的代码。如果不知道如何处理，可以参考下面的模板：
Python这样写：
python
while(True):
   	try:
       ...
   	except EOFError:
       break
C++这样写：
while(cin>>x>>y) { 求x和y最大公约数的代码 }
C这样写：
while(scanf(%x %y",&x,&y)!=EOF) { 求x和y最大公约数的代码 }

python

# 求两个整数的最大公约数
def comfac(a, b):
    n = 1
    for i in range(1, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            n = i
    return n

while True:
    try:
        a, b = map(int, input().split())
    except:
        break
    print(comfac(a, b))

用math.gcd

python

from math import gcd

while True:
    try:
        a, b = input().split()
        print(gcd(int(a), int(b)))
    except EOFError:
        break

自己实现gcd

python

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def main():
    import sys
    input = sys.stdin.read
    data = input().strip().split('\n')

    for line in data:
        a, b = map(int, line.split())
        print(gcd(a, b))

if __name__ == "__main__":
    main()

递归实现gcd

python

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def main():
    import sys
    input = sys.stdin.read
    data = input().strip().split('\n')

    for line in data:
        a, b = map(int, line.split())
        print(gcd(a, b))

if __name__ == "__main__":
    main()

03248: 最大公约数 ​

03248: 最大公约数