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

この記事の所要時間: 228

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*}

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

この方法では \(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. より少し速く, \(4.81\times 10^{-4}\) 秒で解けました.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加