Problem249 素数の部分集合和

問題

S = {2, 3, 5, ..., 4999} を 5000 より小さい素数の集合とする.

要素の合計が素数となるような, S の部分集合の数を求めよ.
最下位の 16 桁を答えとして入力せよ.

ソース

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

class Program
{
    const long Hou = 10000000000000000;

    const int Jyougen = 4999;

    static int[] mSosuuArr;

    //エラトステネスの篩
    static void Eratosthenes()
    {
        var IsSosuuArr = new System.Collections.BitArray(Jyougen + 1);

        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            IsSosuuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSosuuArr.Count - 1; I++) {
            if (I != 2 && I % 2 == 0) continue;

            if (IsSosuuArr[I]) {
                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);

        mSosuuArr = SosuuList.ToArray();
    }

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

        Eratosthenes();

        int SumVal = mSosuuArr.Sum();

        //場合の数[和]なDP表
        long[] DPArr = new long[SumVal + 1];
        DPArr[0] = 1;

        int StaInd = 0;
        for (int I = 0; I <= mSosuuArr.GetUpperBound(0); I++) {
            for (int J = StaInd; 0 <= J; J--) {
                if (DPArr[J] == 0) continue;

                int NewJ = J + mSosuuArr[I];
                DPArr[NewJ] += DPArr[J];
                DPArr[NewJ] %= Hou;
            }
            StaInd += mSosuuArr[I];
        }

        long Answer = 0;
        for (int I = 0; I <= DPArr.GetUpperBound(0); I++) {
            if (DPArr[I] > 0 && IsPrime(I)) {
                Answer += DPArr[I];
                Answer %= Hou;
            }
        }
        Console.WriteLine("Answer={0}。経過時間={1}", Answer, sw.Elapsed);
    }

    //試し割りで素数かを判定
    static bool IsPrime(long pTarget)
    {
        if (pTarget == 2) return true;
        if (pTarget % 2 == 0) return false;
        for (long I = 3; I * I <= pTarget; I += 2) {
            if (pTarget % I == 0) return false;
        }
        return true;
    }
}

実行結果

Answer=9275262564250418。経過時間=00:00:15.5776796

解説

動的計画法で解いてます。