プロジェクトオイラー5.

この記事の所要時間：約 2分38秒

No.5 Smallest multiple

問題.

Q. 2520 は, 1 から 10 のすべてで割り切れる最小の数です.

では, 1 から 20 のすべてで割り切れる最小の数はいくつか.

要は 1 から 20 までの数の最小公倍数を求める問題です.

考え方とプログラム例(Python)

1. 1から順に最小公倍数を求めていく

2つの引数 ( $a, b$ ) の最大公約数 $G$ を返す関数 $gcd(a, b)$ を, ユークリッドの互除法を用いて再帰関数で定義します.

2つの数 $a, b$ の最小公倍数 $L=lcm(a, b)$ は, 最大公約数を $G$ とすると,

$\begin{equation*} L = \dfrac{a\times b}{G} \end{equation*}$

で求まります.

後は,

$\begin{equation*} lcm(lcm(\ldots lcm(lcm(1, 2), 3), \ldots, 20)) \end{equation*}$

を求めれば答えになります.

def gcd(a,b):
	if a == 0 or a == b :
		return b
	if b == 0:
		return a
	if a < b:
		c = a
		a = b
		b = c
	return gcd(a % b, b)
def lcm(a, b):
	return (a * b / gcd(a, b))
n = 1
for i in xrange(1, 21):
	n = lcm(n, i)
print n

def gcd(a,b):

if a == 0 or a == b :

return b

if b == 0:

return a

if a < b:

c = a

a = b

b = c

return gcd(a % b, b)

def lcm(a, b):

return (a * b / gcd(a, b))

n = 1

for i in xrange(1, 21):

n = lcm(n, i)

print n

この方法では $7.73\times10^{-4}$ 秒で答えが求まりました.

2. 素数がいくつ答えに含まれるかを考える

数学的な工夫をして答えを求めていきます.

20以下の素数は, 2, 3, 5, 7, 11, 13, 17, 19 の8個です.

(下のプログラムではエラトステネスの篩によって20以下の素数を求めています. )

すると, 1～20の最小公倍数 $X$ は,

$\begin{equation*} X = 2^{q_2}\times 3^{q_3}\times\cdots\times17^{q_{17}}\times19^{q_{19}} \end{equation*}$

という形になります.

このとき, 20 以下に $2^{q_2}$ の倍数が含まれていて, $2^{q_2+1}$ の倍数は含まれていないことになるので,

$\begin{equation*} q_2 = \left\lfloor\log_{2}{20}\right\rfloor \end{equation*}$

です. 他の素数 $p$ に対する $q_p$ も同様に求められます.

import math
ans = 1
num = [0] * 20
num[0] = 1
for i in xrange(20):
	if num[i] == 0:
		ans *= (i+1)**(int(math.log(20, i+1)))
		n = 2*(i+1)
		while n <= 20:
			num[n-1] = 1
			n += (i+1)
print ans

import math

ans = 1

num = [0] * 20

num[0] = 1

for i in xrange(20):

if num[i] == 0:

ans *= (i+1)**(int(math.log(20, i+1)))

n = 2*(i+1)

while n <= 20:

num[n-1] = 1

n += (i+1)

print ans

この方法では, 1. より少し速く, $4.81\times 10^{-4}$ 秒で解けました.

答えはこの下の行にあります. 反転してください.

A. 232792560

プロジェクトオイラー5.

No.5 Smallest multiple

問題.

考え方とプログラム例(Python)

1. 1から順に最小公倍数を求めていく

2. 素数がいくつ答えに含まれるかを考える

共有:

関連

関連記事