1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2015-02-27

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つのアプローチがあるが、計算量を節減するため、後者をとった。
pe5.png

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回実行)
pe5_2.png

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?