プロジェクトオイラー問249 - sinapusu2002 @ ウィキ

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

Problem 249 「素数の部分集合和」 †
S = {2, 3, 5, ..., 4999} を 5000 より小さい素数の集合とする.

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

何も考えない漸化式ですが、２０１３年の廉価パソコンで計算時間1分の解。
古いパソコンでも１分以内で答えが出るように問題設定されてるはずなので私の解法はかなり遅い。

#include<stdio.h>
#include<iostream>
#include<vector> 

const __int64 L=pow(10,8);
const __int64 LIMIT=L*L;
const int UP=1600*1000; 

std::vector<bool> isP;
std::vector<__int64> cs;

std::vector<__int64> ps;

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

int main(){
	__int64 ans=0;
	for(int i=2;i<5000;i++){
		if(isPrime(i)){
			ps.push_back(i);
		}
	}
	for(int i=0;i<UP;i++){
		isP.push_back(true);
		cs.push_back(0);
	}
	isP[0]=isP[1]=false;
	for(int i=2;i*i<UP;i++){
		if(isP[i]==false)continue;
		for(int j=i*2;j<UP;j+=i){
			isP[j]=false;
		}
	}
	cs[0]=1;
	int sum=0;
	for(int i=0;i<ps.size();i++){
		int p=ps[i];
		for(int j=sum;j>=0;j--){
			cs[j+p]=(cs[j]+cs[j+p])%LIMIT;
		}
		sum+=p;
	}
	for(int i=0;i<UP;i++){
		if(isP[i]==true){
			ans=(ans+cs[i])%LIMIT;
		}
	}
	std::cout<<ans<<"\n";
}