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{align*}
L = \dfrac{a\times b}{G}
\end{align*}
で求まります.
後は,
\begin{align*}
lcm(lcm(\ldots lcm(lcm(1, 2), 3), \ldots, 20))
\end{align*}
を求めれば答えになります.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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{align*}
X = 2^{q_2}\times 3^{q_3}\times\cdots\times17^{q_{17}}\times19^{q_{19}}
\end{align*}
という形になります.
このとき, 20 以下に \(2^{q_2}\) の倍数が含まれていて, \(2^{q_2+1}\) の倍数は含まれていないことになるので,
\begin{align*}
q_2 = \left\lfloor\log_{2}{20}\right\rfloor
\end{align*}
です. 他の素数 \(p\) に対する \(q_p\) も同様に求められます.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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}\) 秒で解けました.
