プロジェクトオイラー1. ~ Multiples of 3 and 5 ~

No.1 Multiples of 3 and 5

問題.

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

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

 

考え方とプログラム例(c++/Python3)

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

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

#include<bits/stdc++.h>
using namespace std;
int main(){
    int ans = 0;
    for(int i = 1; i < 1000; i++){
        if(i % 3 == 0 || i % 5 == 0)
            ans += i;
    }
    cout << ans << endl;
    return 0;
}

pythonを使えば1行で書くこともできます．

print(sum([n for n in range(1, 1000) if n % 3 == 0 or n % 5 == 0]))

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

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

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

で求まります.

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

のように求められます.

#include<bits/stdc++.h>
using namespace std;
int Sum(int a, int n){
	int m = (n-1) / a;
	return (a * m * (m+1) / 2);
}
int main(){
    int ans = Sum(3, 1000) + Sum(5, 1000) - Sum(15, 1000);
    cout << ans << endl;
    return 0;
}