C#でプロジェクトオイラーを解く（問題４７「異なる素因数」）

Tweet

Pocket

どーも、みつおです。

問題

それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:

14 = 2 × 7
15 = 3 × 5

それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:

644 = 2^2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?

出典：Problem47

解答

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

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

        private static long Solve()
        {
            long ret = 0;
            int i = 1;
            int cnt = 0;

            while(true)
            {
                //素因数分解
                var soinsubunkai = SoinsuBunkai(i);

                //重複削除
                var tmpsoinsu = soinsubunkai.Distinct();

                //異なる４つの素因数か判定
                if (tmpsoinsu.Count() == 4) cnt++;
                else cnt = 0;

                //連続する4つか判定
                if(cnt == 4) break;

                //iをインクリメント
                i++;
            }

            //連続する4つの最初の数を取得
            ret = i - cnt + 1;

            return ret;
        }

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

            while (i * i <= n)
            {
                if (tmp % i == 0)
                {
                    tmp /= i;
                    yield return i;
                }
                else i++;
            }

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

出力

134043