POJ 2739 Sum of Consecutive Prime Numbers
問題
http://poj.org/problem?id=2739
はじめ英語の問題文の解釈を間違っていて、
(連続していなくてもいいと思って動的計画法とか試していた)
1時間ぐらい無駄にしてしまった。
解法
10000以下の素数の個数は
P=1229個だから可能な連続した素数の和をすべて試しても制限時間に収まる。
(1クエリあたりO(P^2) )
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 10001; const int MAX_P = 1229; bool p[MAX_N]; int pl[MAX_P]; int pn; int main(){ pn = 0; fill(p, p + MAX_N, true); p[0] = p[1] = false; for(int i=2;i<MAX_N;i++){ if(p[i]){ for(int j=i*2;j<MAX_N;j+=i){ p[j] = false; } pl[pn] = i; pn++; } } int N; while(scanf("%d", &N) &&N){ int ans = 0; for(int i = 0; i < pn; i++){ int sum = 0; for(int j = i; j < pn; j++){ if(pl[j] > N) break; sum += pl[j]; if(sum == N) ans++; if(sum >= N) continue; } } printf("%d\n", ans); } return 0; }