プロジェクトオイラー Problem5

「プロジェクト　オイラー」の問題をpythonでやってみます。

出典：Project Euler（日本語翻訳サイト）
参考：サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 5
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。
では、1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。

私の解答例は以下のとおりです。
－－－－－

def gcd(a, b):
 if a<b: a, b = b, a
 if b: return gcd(b, a%b)
 else: return a
 
def lcm(a, b): return a*b/gcd(a,b)
 
def f(n):
 t = 1
 for i in xrange(1, n+1):
  t = lcm(t, i)
 return t
 
print f(20)

－－－－－

関数を３つ使います。

１．関数gcd(a, b)
　aとbの最大公約数(Greatest Common Divisor)を返します。
　ロジックは 以下の数学公式 を利用した解き方です。
「a≧bのとき、aとbの最大公約数は、bと"a/bの余り"の最大公約数と等しい」

「ユークリッドの互除法」と呼ばれている解法です。（参考： wikipedia ）

・if a<b: a, b = b, a
　aとbのうち、大きい方をaにします。bの方が大きいときは入れ替えます。

・if b:
　文の条件式は、Trueが0以外で、Falseが0です。
　小さい方の数bが0になるまで、小さい方の数bとaをbで割った余り(a%b)で当関数を再帰呼び出し（自分で自分自身を呼び出すこと）します。

２．関数lcm(a, b)
　aとbの最小公倍数(Least Common Multiple)を返します。
　ロジックは数学公式の「２数の積はそれらの最小公倍数と最大公約数の積に等しい」を使用し、aとbの積を最大公約数で割った値を最小公倍数として返します。

なお、上記の数学公式の証明は以下のとおりです。
　aとbの最大公約数をGとすると、２数a,bとその最小公倍数Lは以下の通りです。
　a = AxG
　b = BxG　（AとBは、互いに素）
　L = AxBxG
　よって、axb = (AxG)x(BxG) = (AxBxG)xG = LxG（証明終り）
　例）a=12,b=18の場合、12=2x6、18=3X6と表せ、
　　　G=6、L=2x3x6=36 です。　12x18 = 6x36。

３．関数f(n)
　n以下の全ての整数の最小公倍数を返します。

・for i in xrange(1, n+1):
　xrange関数は[1, 2, ・・・, n]と同じ意味です。
　今までの最小公倍数tとループ変数iの最小公倍数tを求め、ループ最後まで繰り返します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
232792560


（追記）
・20120716
　ソースコード部分にSyntaxHighlighterを導入。