プロジェクトオイラー Problem 77 「素数の和」 †

Problem 77 「素数の和」 †

10は素数の和として5通りに表すことができる:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

素数の和としての表し方が5000通り以上になる最初の数を求めよ.

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

解法
素数だけを対象にした動的計画法で計算がすみます。
5000通りは少ないので
50000000000通りを超える場合を計算させていますが動的計画法なのでもちろん一瞬で答えが出ます。
コード中の
 if(sum>=50000000000)break;
を
 if(sum>=5000)break;
とすれば5000通りを超える場合が計算できます。




#include<stdio.h>
#include<vector>
#include<map>
#include<iostream>
bool is_prime(int num){
      if(num<2)return false;
      for(int i=2;i*i<=num;i++){
            if(num%i==0)return false;
      }
      return true;
}

int main(){
      std::map<int, std::map<int,__int64> > dp;
      std::map<int,__int64> map;

      std::map<int, __int64>::iterator it;
      std::vector<int> primes;
      dp[0][0]=0;
      int num=2;
      while(1){
            __int64 sum=0;
            if(is_prime(num)){
                  primes.push_back(num);
            }
            for(int i=0;i<primes.size();i++){
                  int p=primes[i];
                  if(dp.find(num-p)!=dp.end()){
                        it=dp[num-p].upper_bound(p);
                        it--;
                        sum+=(*it).second;
                  }
                  dp[num][p]=sum;
            }
            if(sum>=50000000000)break;
            if(is_prime(num)){
                  if(dp.find(num)==dp.end())dp[num]=map;
                  dp[num][num]=sum+1;
                  dp[num][0]=0;
            }
           
            num++;
      }
      printf("%d\n",num);
}