Pythonでユークリッドの互除法

GCD

mathモジュールに最大公約数（GCD）を求める関数が無いようなので作ってみた。
アルゴリズムの説明はWikipediaに載っている。

cf. http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95

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


if __name__ == '__main__':
    import sys

    a = int(sys.argv[1])
    b = int(sys.argv[2])
    print gcd(a, b)

実行例：

^o^ > python gcd.py 24 36
12

LCM

ついでに最小公倍数（LCM）もやってみた。

import gcd

def lcm(a, b):
    return a * b / gcd.gcd(a,b)


if __name__ == '__main__':
    import sys

    a = int(sys.argv[1])
    b = int(sys.argv[2])
    print lcm(a, b)

実行例：

^o^ > python lcm.py 24 36
72

追記

よくよく調べたらfractionsモジュールにgcd関数があった。

>>> import fractions
>>> fractions.gcd(24, 36)
12