読者です 読者をやめる 読者になる 読者になる

Project Euler : Problem1『Multiples of 3 and 5』

プログラミング 算数 C#


iPam - Jim!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);
        }
    }
}
感想

 なるほど感がある。


オイラーの公式がわかる (ブルーバックス)

オイラーの公式がわかる (ブルーバックス)

Project Euler

Project Euler

Project Euler

Project Euler