ユークリッドの互除法で最大公約数を求める

今日は、２つの整数 m と n の最大公約数を

ユークリッドの互除法で求めるアルゴリズムです。

ユークリッドの互除法とは、

「２つの整数 m と n　(m > n)があったとき、mとnの最大公約数は

m-n と n の最大公約数を求める方法に置き換えることができる」

という原理だそうです。

具体的には、m-n (m < n なら n -m) を mとn が等しくなるまで繰り返す。

mとnが等しくなったらそれが、最大公約数となる。

例として、m=24, n=18 で計算してみよう。

m - n = 24 - 18 = 6 これを新たなmとする

m < n なので、　n - m = 18 - 6 = 12 これを新たなnとする。

同じく、m < n なので、 n - m = 12 - 6 = 6 これを新たなnとする。

ここで、m = nとなるので計算はやめる。

m = n となった「６」が最大公約数となる。

以上、をふまえ

【問題】

ユークリッドの互除法で最大公約数を求めるには？

【回答】

import sys

m = int(sys.argv[1])

n = int(sys.argv[2])

print str(m) + 'と' + str(n) + 'の最大公約数は',

while(m <> n):

  if(m > n):

    m -= n

  else:

    n -= m

print str(m) + 'です。'

【実行結果】

> python euclid.py 24 18

24と18の最大公約数は 6です。

> python euclid.py 50 5

50と5の最大公約数は 5です。

> python euclid.py 49 42

49と42の最大公約数は 7です。

もっとpythonらしいコーディングのしかたがあると思うのですが

まだ、駆け出しのpyer(パイラー）なもんで、

ご勘弁を。