C#でプロジェクトオイラーを解く（問題５「最小の倍数」）

Tweet

Pocket

どーも、みつおです。

問題

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

出典：Problem5

解答

using System;
using System.Collections.Generic;
using System.Linq;

namespace Problem5
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();
        }

        private static long Solve()
        {
            long ret = 0;

            int No = 20;
            List<int> soinsubunkailist = new List<int>();

            //20から1ずつ減らすループ
            for (int i = No; 1 <= i; i--)
            {
                //iを素因数分解（すでに素因数分解のリストに値がある場合は追加しない）
                var soinsubunkai = YetData(i, soinsubunkailist);

                foreach (var tmp in soinsubunkai)
                {
                    //素因数分解のリストに追加
                    soinsubunkailist.Add(tmp);
                }
            }

            //１～２０の素因数分解（重複削除）の積
            ret = soinsubunkailist.Aggregate((now, next) => now * next);

            return ret;
        }

        public static List<int> YetData(int n, List<int> data)
        {
            List<int> ret = new List<int>();
            List<int> tmp = new List<int>(data);

            //nを素因数分解
            var soinsu = SoinsuBunkai(n);

            foreach (var num in soinsu)
            {
                //素因数分解のリストにある場合、
                if (!tmp.Remove(num)) ret.Add(num);
            }

            return ret;
        }

        public static IEnumerable<int> SoinsuBunkai(int n)
        {
            int i = 2;
            int tmp = n;

            //合成数xはp≤√xを満たす素因子pをもつという性質を利用
            while (i * i <= n)
            {
                //iで割り切れるか判定
                if (tmp % i == 0)
                {
                    tmp /= i;
                    yield return i;
                }
                else i++;
            }

            if (tmp != 1) yield return tmp;
        }
    }
}

出力

232792560