Dr Wu 3 uva 3399 (Live)

Problem Link

Sieve + Prefix Sum + Binamry Search (STL Map)

Complexity : O(sieve) + O(X*log(X))  ; where X = number of prime numbers in the range

Code :-
 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

using namespace std; bool isPrime[10009]; int prefix_sum[10009]; map<int,int>Bin_Search; int num_primes; void sieve(int N) { int sqN = sqrt(N) + 5; for(int i = 2; i<=sqN; i++) { if(isPrime[i]) { num_primes++; for(int j=2*i; j<=N; j+=i) { isPrime[j] = false; } } } } int main() { ms(isPrime,true); num_primes = 0; sieve(10002); int idx = 1; prefix_sum[0] = 0; loop(x,2,10002) { if(isPrime[x]) { prefix_sum[idx] = prefix_sum[idx-1] + x; int val = prefix_sum[idx]; Bin_Search[val] = 1; idx++; } } while(true) { int inp; cin>>inp; if(inp==0) return 0; int ans = 0; loop(x,1,idx-2) { int leftToSearch = prefix_sum[x] - inp; if(leftToSearch==0) ans++; if(leftToSearch<0) continue; if(Bin_Search[leftToSearch]!=0) { ans++; } } cout<<ans<<endl; } return 0; }