Project Euler : Problem1『Multiples of 3 and 5』

iPam - Jim! / marc kjerland

　projecteuler.net
数学的問題をプログラムで解きましょうね、というサイト。
週1で新しい問題が追加されるのかな？

問題1『3および5の倍数』

　英語じゃなくて日本語がいいです(本音)

問題の内容は、「1000未満の自然数のうち、3および5の倍数の総和を求めよ」という問題。

ループぶん回せばいいんでしょ？

　という考えで作ったのがこちらになります。

using System;
using System.Diagnostics;

namespace Problem1
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(solv1());
        }

        static int solv1()
        {
            int sum = 0;

            for (int i = 1; i < 1000; i++)
            {
                if ((i % 3 == 0) | (i % 5 == 0))
                {
                    sum += i;
                }
            }

            return sum;
        }
    }
}

　単純に1000までの数字を1つ1つ見ていき、「あ、これ3(または5)の倍数や！」と気づいたら足していくという処理。
答え出すだけなら別にこれでもいいんだけど。

より良い方法

　Wikipediaを見て、より良い方法があるのを知った。
プロジェクト・オイラー - Wikipedia
　包除原理や閉形式総和なんて難しい言葉使ってるけど、要は
3の倍数の総和と5の倍数の総和を足して、ダブルカウント状態にある15の倍数、その総和を引く。
ということ。

Wikipediaの方法

　何かもう、見るからに計算量少なくて済むのがわかりますよね。

using System;
using System.Diagnostics;

namespace Problem1
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(solv2());
        }

        static int solv2()
        {
            return SumM(1000, 3) + SumM(1000, 5) - SumM(1000, 15);
        }

        static int SumM(int MaxValue, int MultipleNumber)
        {
            int n = (MaxValue - 1) / MultipleNumber;

            return MultipleNumber * ((n * (n + 1)) / 2);
        }
    }
}