두 수의 gcd를 구하는 파이썬 스크립트

과제 때문에 작성한 스크립트인데 블로그 포스트로 괜찮을 것 같아서 올린다.

gcd.py:


# -*- coding: utf-8 -*-
 
import argparse
 
 
def gcd(a, b):
    mx = max(a, b)
    mn = min(a, b)
    d = mx // mn
    rest = mx % mn
    assert (d * mn + rest) == mx
    if rest == 0:
        return mn
    return gcd(mn, rest)
 
 
def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("a", type=int)
    parser.add_argument("b", type=int)
    args = parser.parse_args()
    v = gcd(args.a, args.b)
    print(v)
 
 
if __name__ == '__main__':
    main()

사용법 (cli)


$ python gcd.py 6 81
3
 
$ python ./gcd.py 25 100
25

사용법 (module)


from gcd import gcd
 
print(gcd(6, 81)) // 3
print(gcd(100, 25)) // 25

구현

Euclidean algorithm을 이용했다.