C#でプロジェクトオイラーを解く（問題４９「素数数列」）

Tweet

Pocket

どーも、みつおです。

問題

項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ.

• (i)3つの項はそれぞれ素数である.
• (ii)各項は他の項の置換で表される.

1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが, 4桁の増加列にはもう1つ存在する.

それではこの数列の3つの項を連結した12桁の数を求めよ.

出典：Problem49

解答

using System;
using System.Linq;

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

        private static long Solve()
        {
            long ret = 0;
            long b, c;
            string ans = "";

            //奇数でループ
            for(int a = 1001;a <= 9999; a += 2)
            {
                if (!IsSosu(a)) continue;

                for (int kousa = 1000; kousa <= 3333; kousa++)
                {
                    b = a + kousa;
                    c = b + kousa;

                    //4桁を超えたら次のループ
                    if (9999 < b || 9999 < c) break;

                    //それぞれが素数か判定
                    if (!IsSosu(b)) continue;
                    if (!IsSosu(c)) continue;

                    //それぞれが置換できるか判定
                    if (!IsSameNum(a, b)) continue;
                    if (!IsSameNum(a, c)) continue;

                    //12桁の数値を算出
                    ans = a.ToString() + b.ToString() + c.ToString();
                    ret = long.Parse(ans);

                    //項差3330の等差数列1487, 4817, 8147は除外
                    if (ret == 148748178147) continue;

                    return ret;
                }
            }

            return ret;
        }

        private static bool IsSameNum(long a, long b)
        {
            bool ret = true;

            //数値を昇順に並び替え
            var stra = a.ToString().OrderBy(tmp => tmp);
            var strb = b.ToString().OrderBy(tmp => tmp);

            //並び替えた数値を比較
            if (stra.SequenceEqual(strb)) ret = true;
            else ret = false;

            return ret;
        }

        private static bool IsSosu(long no)
        {
            bool ret = true;

            //数値が2未満（1)なら素数じゃない、2なら素数
            if (no < 2) return false;
            else if (no == 2) return true;

            //数値が2で割り切れるなら素数じゃない
            if (no % 2 == 0) return false;

            //合成数xはp≦√xを満たす素因子pをもつ
            double sqrtno = Math.Sqrt(no);

            //奇数でループ 
            for (int i = 3; i <= sqrtno; i += 2)
            {
                //割り切れるので素数じゃない
                if (no % i == 0) return false;
            }

            return ret;
        }
    }
}

出力

296962999629