プロジェクトオイラー Problem 249 「素数の部分集合和」 †

Problem 249 「素数の部分集合和」 †

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

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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20249





解法
これも問250と同じサービス問題のようで難易度は低いです。
ただ私の発想が悪いのか動的計画法の本体で速度がでてません。
オーソドックスな動的計画法を書いたつもりなのですが？
たぶんmod演算が遅いのでmod演算を実行回数へらしたらいいのかもしれません。
そう考えてmod演算を引き算に置き換えてみたところ驚くほど高速化しました。
Ｍｏｄ演算が遅いのはＣＰＵが悪いのかもしれません。



#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
__int64 dp[1600000];

bool is_prime(int n){
      if(n<2)return false;
      for(int i=2;i*i<=n;i+=1+(i&1)){
            if(n%i==0)return false;
      }
      return true;
}

int main(){
   
      __int64 MOD_LIMIT=100000000;
      MOD_LIMIT*=100000000;
      memset(dp,0,sizeof(dp));
      int now,next,sum=0;
      std::vector<int> primes;
      for(int i=2;i<5000;i++){
            if(is_prime(i)){
                  primes.push_back(i);
            }
      }
      for(int i=0;i<primes.size();i++){
            int p=primes[i];
            sum+=p;
            for(int j=sum;j>=p;j--){
                  dp[j]=(dp[j]+dp[j-p]);
                  if(dp[j]>=MOD_LIMIT)dp[j]-=MOD_LIMIT;
            }
            dp[p]+=1;
      }
      __int64 ans=0;
      for(int j=2;j<=sum;j++){
            if(is_prime(j)==true){
                  ans=(ans+dp[j])%MOD_LIMIT;
            }
      }
      std::cout<<ans<<"\n";
}