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

この記事の所要時間: 150

No.1 Multiples of 3 and 5

問題.

Q. 10 未満で, 3 又は 5 の倍数は 3, 5, 6, 9 の 4 つで, それらの総和は 23 となる.

では, 1,000 未満で 3 又は 5 の倍数であるものの総和はいくらか.

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

1. シンプルにループで和を求める

1,000 未満とあまり大きな数ではないので, 1~999 のすべての数について 3 or 5 の倍数かどうかを調べて足しあげていきます.

計算時間は7.29\times 10^{-4}秒でした.

これをpython らしいコードで書いてみると2行で済みます.

2. 1からの自然数の和の公式を用いる

3 または 5 の倍数の総和は,

(3 の倍数の総和) + (5 の倍数の総和) – (15 の倍数の総和)

で求まります.

例えば, 3 の倍数は 3, 6, \ldots, 999 の333個で, その和は, 公式を使って,

\begin{eqnarray*} 3+6+\ldots+999 &=& 3(1+2+\ldots+333)\\ &=& 3\cdot \dfrac{1}{2}\cdot 333\cdot (333+1)\\ &=& 166833 \end{eqnarray*}

のように求められます.

この場合計算時間は3.70\times 10^{-4}秒でした.

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

A. 233168

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