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

この記事の所要時間: 238

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

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

この方法では 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 も同様に求められます.

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

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

A. 232792560

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