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

この記事の所要時間: 136

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{align*}
3+6+\ldots+999 &= 3(1+2+\ldots+333)\\
&= 3\cdot \dfrac{1}{2}\cdot 333\cdot (333+1)\\
&= 166833
\end{align*}

のように求められます.

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

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