C#で Project Euler P1
はじめに
暇だったのでやってみた。
本家 : About - Project Euler
日本語: Project Euler - PukiWiki
テンプレート
using System; public static class P { public static void Main() { Console.WriteLine(Calc()); } private static int Calc() { } }
これに対し、クラス名に問題番号を付けてCalcメソッドを実装する形でやっていこうと思います。
また、問題も載せますが日本語訳された方から引用します。
問題
Problem 1 「3と5の倍数」
10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.
Problem 1 - PukiWiki
解答
using System; public static class P1 { [STAThread] public static void Main() { Console.WriteLine(Calc()); } private static int Calc() { return Sum(3) + Sum(5) - Sum(3 * 5); } private static int Sum(int n) { var m = (1000 - 1) / n; return (n * (1 + m)) * m / 2; } }
計算量 O(1)
3の倍数と5の倍数それぞれの総和から重複してるところを引く。
等差数列なので繰り返しなしで求められる。