Output練習のためProjectEulerを解いてみる #1

本日から、コーディング力の向上とアウトプットする力を高めるために、毎週一問ProjectEulerの問題を解いてみようと思います。いろいろ至らない点もあると思いますが、ご容赦いただければと思います。

ProjectEulerとは

数学の問題をプログラムを用いて解くサイトです。最初の100問までは答えを掲載してもよいという規則があるので、そこまで記事を書くことを目指していこうと思います。

マイルール

• 拡張性を持たせる
  　条件として、N　＜＝　1000000　とかがあるのですが、その条件を厳しくしても成り立つようなコードを書いていこうと思います
• 一つのコードで完結させる
  　前処理とかが必要な問題でも、なるたけ一つのコードで完結させるようなコードを書きたいと思います。
• 読みやすいコードを書く
  基本的には、コーディング規約とリーダブルコードに従ったコードを書いていきます。

では早速解いていこうと思います。

#1 Multiples of 3 or 5

問題文　If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

和訳

#1 3か5の倍数
10未満の3か5の倍数をすべてリストアップすると、3,5,6,9が得られる。これらの倍数の合計は23である。
1000未満の3か5の倍数をすべて合計した数を求めよ

方針

変則的なFizzBuzzといった感じ。求める数をSとしたとき

S = (1から999までの3の倍数の和) + (1から999までの5の倍数の和) - (1から999までの15の倍数の和)

で表せるので、1から1000までの数を順番に調べればよし。

コード

ProjectEuler_1.py

N = 1000
ans = 0
for n in range(1, N):
    if n % 3 == 0:
        ans += n
    if n % 5 == 0:
        ans += n
    if n % 15 == 0:
        ans -= n
print(ans)

答えとして、233168が得られる。

展望

計算量はO(N)で十分早いとは思うが、工夫することで、簡単にO(1)にできそう。あとは、今回は素因数が2種類だけだったが、種類が増えた場合に対応したバージョンを作ってみても面白そう。