Cマガ電脳クラブ(第110回) 欲張りな2数

問題

ここに「56097」と「14128」という5桁の数がある。
この2数の和は「70225」で、265の2乗、つまり平方数となっている。
また、差は「41969」で、素数となっている。
さらに、積は「792538416」で、なんと小町数となっているのだ。このように、
  (1) A＋Bが平方数になる
  (2) A−Bが素数になる
  (3) A×Bが小町数になる
という3つの条件を同時に満たす5桁の正の整数 A, B (ただしA>B) のペアをすべて求めていただきたい。
前述の例を含めて何通りあるだろうか。
なお、小町数とは，1〜9の数字がすべてひとつずつ登場している9桁の数のことである。

ソース

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

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        //平方数の配列を返す
        int[] HeihousuuArr = DeriveHeihousuuArr();

        //エラトステネスの篩で5桁の最大値以下の素数の配列を返す
        int[] SosuuArr = Eratosthenes();

        int AnswerCnt = 0;

        //AとBのペアを列挙
        for (int LoopA = 10000; LoopA <= 99999; LoopA++) {
            //10の倍数なら積が小町数にならない
            if (LoopA % 10 == 0) continue;

            for (int LoopB = 10000; LoopB < LoopA; LoopB++) {
                int Wa = LoopA + LoopB;
                int Sa = LoopA - LoopB;
                int Seki = LoopA * LoopB;

                //小町数の最大値を超えたらBreak
                if (Seki > 987654321) break;

                if (Array.BinarySearch(HeihousuuArr, Wa) < 0)
                    continue;
                if (Array.BinarySearch(SosuuArr, Sa) < 0)
                    continue;
                if (IsKomatiSuu(Seki) == false) continue;

                AnswerCnt++;
                Console.WriteLine("解{0}を発見。経過時間={1}", AnswerCnt, sw.Elapsed);
                Console.WriteLine("A={0},B={1},和={2},差={3},積={4}",
                    LoopA, LoopB, Wa, Sa, Seki);
            }
        }
    }

    //平方数の配列を返す
    static int[] DeriveHeihousuuArr()
    {
        var WillReturn = new List<int>();

        const long MinVal = 10000 + 10000;
        const long MaxVal = 99999 + 99999;

        //5桁+5桁の最小値から最大値までの平方数を列挙
        for (int I = 0; I * I <= MaxVal; I++) {
            if (I * I < MinVal) continue;
            WillReturn.Add(I * I);
        }
        return WillReturn.ToArray();
    }

    //エラトステネスの篩で5桁の最大値以下の素数の配列を返す
    static int[] Eratosthenes()
    {
        var IsSosuuArr = new System.Collections.BitArray(99999 + 1);
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            IsSosuuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I] == false) continue;
            for (int J = I * 2; J <= IsSosuuArr.Count - 1; J += I) {
                IsSosuuArr[J] = false;
            }
        }
        var SosuuList = new List<int>();
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I]) SosuuList.Add(I);
        }
        return SosuuList.ToArray();
    }

    //小町数かを判定
    static bool IsKomatiSuu(int pTargetNum)
    {
        if (pTargetNum < 123456789) return false;
        if (pTargetNum > 987654321) return false;

        bool[] IsAppearedArr = new bool[10];

        int CopiedVal = pTargetNum;
        do {
            int ModVal = CopiedVal % 10;

            //0を含んだらNG
            if (ModVal == 0) return false;

            //同じ数字を2個以上含んだらNG
            if (IsAppearedArr[ModVal]) return false;
            IsAppearedArr[ModVal] = true;
        } while ((CopiedVal /= 10) > 0);
        return true;
    }
}

実行結果

省略
解66を発見。経過時間=00:01:49.0935878
A=64998,B=11731,和=76729,差=53267,積=762491538
解67を発見。経過時間=00:01:50.2010532
A=66238,B=13851,和=80089,差=52387,積=917462538
解68を発見。経過時間=00:01:51.4849158
A=67752,B=11209,和=78961,差=56543,積=759432168
解69を発見。経過時間=00:01:56.7840055
A=75546,B=11479,和=87025,差=64067,積=867192534
解70を発見。経過時間=00:01:57.6842366
A=77287,B=12114,和=89401,差=65173,積=936254718

解説

事前に平方数と素数を配列で求めておいて、バイナリサーチを使ってます。