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
カテゴリー: algorithm, Python パーマリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください