두 수의 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을 이용했다.