Project Euler 5 「最小の倍数」３つの回答方法を考えてみた。

4853 ワード
ProjectEuler Python Python テキストリンク

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205

「最小の倍数」 †
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205

回答案1
ユークリッドの互除法を使用する。
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(m,n):
  while n != 0:
    (m,n) = (n,m%n)
  return m

def lcm(m,n):
  return m*n/gcd(m,n)

def cof1():
  max = 20
  i = 6
  for j in range(5,max+1):
    i = lcm(i,j)
  #print i

回答案2
次のように素因数分解できる数m,nの最小公倍数は、
m = p1^n1 * p2^n2
n = p1^n3 * p3^n4

同一の素数を含む（上記だとp1)→指数n1,n3の大きい方をとったp1^(max(n1,n3)を因子にもつ。
一方にしかない素数(上記だとp2,p3)→p2^n2, p3^n4を因子にもつ。

→数を素因数分解して{素数:指数}という辞書で表し、上記の計算から最小公倍数を求める。

上記を以前作ったmymathを使って以下のように実装してみた。
http://qiita.com/cof/items/45d3823c3d71e7e22920

import mymath
def cof2():
  max = 20
  pri = mymath.get_primes(max)
  num1 = mymath.factor_dict(2,pri)
  for i in range(3,max+1):
    num2 = mymath.factor_dict(i,pri)
    num1 = mymath.lcm_dict(num1,num2)
  ans = mymath.dict2num(num1)
  print ans

回答案3
1からmaxまで連続する数の最小公倍数Lは、max以下の素数p1,p2,‥を用いて
L = p1^n1 * p2^n2 * p3^n3‥
と表せる。

ここで、各p1^n1はmax以下である。
これを求めるのに、以下の2つのアプローチがあるが、計算量を節減するため、後者をとった。

import mymath
def cof3():
  max = 20
  #20までの素数列を生成
  pri = mymath.get_primes(max)
  ans = 1
  j=1
  i=-1
  while i!=0:
    i=0
    #素数それぞれを、その累乗数がmaxを超えない範囲で答えに掛け合わせる
    while i < len(pri['list']) and pri['list'][i]**j <= max:
      ans *= pri['list'][i]
      i+=1
    j+=1

  #print ans

3つほど試すも、結果として　やはりユークリッドの互除法が最速。ユークリッド先生ぱないっす。(10,000回実行)