Project Euler : Problem 49 『Prime permutations』

問題

projecteuler.net
日本語訳→http://www.odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2049

4桁の素数を全部出します

　一瞬です

等差数列の素数を選びます

　3つの素数P_m, P_n, P_oが公差dの関係になってるとのことなので、
素数P_mと素数P_o (m < o)を選び、d = (P_o - P_m) / 2から
P_n = P_m + d が存在するか調べます。

使ってる字は一緒か調べる

　素数P_m, P_n, P_oを文字列にしてソートします。
同じ数字を使ってるならソート結果は同一になるはずなので、あとはチェックするだけです。

コード

using System;
using System.Linq;

namespace ProjectEuler.Problem49
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] primes = ES(1000, 10000);

            for (int i = 0; i < primes.Length; i++)
            {
                for (int sp = primes.Length - 1; sp >= i + 2; sp--)
                {
                    int v = primes[i] + (primes[sp] - primes[i]) / 2;

                    if (Array.BinarySearch(primes, v) >= 0)
                    {
                        if (CheckNumber(primes[i].ToString(), v.ToString(), primes[sp].ToString()) == true)
                        {
                            Console.WriteLine($"{primes[i]}{v}{primes[sp]}");
                        }
                    }
                }
            }
        }

        /// <summary>
        /// 各項は置換可能な数字か調べる
        /// </summary>
        static bool CheckNumber(string p1, string p2, string p3)
        {
            char[] s1 = p1.OrderBy(x => x).ToArray();
            char[] s2 = p2.OrderBy(x => x).ToArray();
            char[] s3 = p3.OrderBy(x => x).ToArray();

            for (int i = 0; i < s1.Length; i++)
            {
                if ((s1[i] != s2[i]) | (s2[i] != s3[i])) return false;
            }

            return true;
        }

        //エラトステネスの篩
        static int[] ES(int min, int max)
        {
            int[] ps = new int[max + 1];

            for (int i = 0; i < ps.Length; i++)
            {
                ps[i] = i;
            }
            ps[1] = 0;

            for (int i = 2; i < ps.Length; i++)
            {
                for (int j = i; j < ps.Length; j++)
                {
                    if (ps[i] != 0) break;
                }

                for (int j = 2 * i; j < ps.Length; j += i)
                {
                    ps[j] = 0;
                }
            }

            return ps.Where(x => x >= min).ToArray();
        }
    }
}