MPRIME1 - Sum of Primes
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#define MAX 11111
int s[MAX];
bool pr[MAX];
int n,c;
int np;
void eratosthene(void) {
int i,j;
np=0;
s[0]=0;
pr[0]=true;
pr[1]=true;
for (i=2;i<MAX;i=i+1)
if (!pr[i]) {
np++;
s[np]=s[np-1]+i;
for (j=2*i;j<MAX;j=j+i) pr[j]=true;
}
}
int bs(int l,int r,int num,int val) {
if (l>r) return (-1);
if (l==r) {
if (s[l+num-1]-s[l-1]==val) return (l);
return (-1);
}
if (r-l==1) {
if (s[l+num-1]-s[l-1]==val) return (l);
if (s[r+num-1]-s[r-1]==val) return (r);
return (-1);
}
int m=(l+r)/2;
if (s[m+num-1]-s[m-1]==val) return (m);
if (s[m+num-1]-s[m-1]>val) return (bs(l,m-1,num,val));
if (s[m+num-1]-s[m-1]<val) return (bs(m+1,r,num,val));
}
void process(void) {
c=0;
int i;
for (i=1;i<=np;i=i+1) c=c+(bs(1,np-i+1,i,n)>0);
printf("%d\n",c);
}
int main(void) {
eratosthene();
while (true) {
scanf("%d",&n);
if (n==0) return (0);
process();
}
}