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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2077
Problem 77 「素数の和」 †
素数の和として5000通り以上の表し方ができる最も小さい数を答えよ。

解法
5000通りなので全探索で済みます。

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

std::vector<int> prime;
int saiki(int p,int n){
 	if(n==0){
		return 1;
	}else{
		int re=0;
		for(int i=p;(i<prime.size())&&(prime[i]<=n);i++){
			re+=saiki(i,n-prime[i]);
		}
		return re;
	}
}

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

int main(){
	prime.push_back(2);
	prime.push_back(3);
	for(int i=4;;i++){
 		if(saiki(0,i)>=5000){
			printf("%d\n",i);
			return 0;
		}
		if(is_prime(i))prime.push_back(i);
	}
}