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();
	}
}

Download