(POJ - 2739) sum of constructive prime numbers (ruler or two points)

Topic link ：Sum of Consecutive Prime Numbers - POJ 2739 - Virtual Judge

Chinese question meaning ：

Small X I like prime numbers very much , So we often study the properties of primes , That day he wanted to know whether a number could be used （ Maybe it's a ） The sum of consecutive prime numbers represents , And want to know how many ways . for example ,53 There are two ways to express 5 + 7 + 11 + 13 + 17 and 53. Prime number v Must be continuous and a prime can only be used once . Now I'll give you an integer n, You have to tell him how many different continuous primes and representations there are for this number .

Input

Multiple sets of data input , One number per line n, When n=0 End of time . n stay 2 And 10000 Between .

Output

One line per output , Output the corresponding answer .

Sample Input

2
3
17
41
20
666
12
53
0

Sample Output

1
1
2
3
0
0
1
2

analysis ： There are two approaches to this topic , The following two methods are analyzed respectively

No matter which method is used, the prime table needs to be preprocessed ,10000 The prime number table of can be pretreated with Ehrlich sieve

The first way ： Ruler method

We use it l and r Represents the sum of the currently selected primes , If less than n, Just make r Add one , If more than n Just make l reduce 1, If the sum of the currently selected primes is equal to n, Makes the ans+1, This will solve the problem , This method is relatively simple , Complexity is o(nlogn)（ Because the complexity of the sieve is nlogn）, It's also easier to implement

The second way ： Two points

We preprocess the prefixes of primes and , Fix the right boundary every time r, Judging whether there is a left boundary satisfying the meaning of the question by dichotomy left boundary makes l To r The sum of primes in is n, The overall complexity is also o（logn）, To optimize a little bit of code , We can dichotomy the bounded maximum in advance , Because the maximum value of the continuous primes we choose must be less than or equal to n Of , So we can choose the first one less than or equal to n As the right boundary , This process is realized by dichotomy , The overall complexity is also o(nlogn), It is complex to realize the method of larger scale

Here are the codes of two methods ：

Ruler method ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=10003;
int prime[N],cnt,s[N];
bool vis[N];
void init()// Preprocess out primes 
{
	for(int i=2;i<=10000;i++)
	{
		if(vis[i]) continue;
		prime[++cnt]=i;
		for(int j=2;j*i<=10000;j++)
			vis[i*j]=true;
	}
}
int main()
{
	init();
	int n;
	while(1)
	{
		scanf("%d",&n);
		if(!n) break;
		int ans=0,p=0;
		for(int i=1,j=1;i<=cnt&&j<=cnt;)
		{
			while(p<n&&j<=cnt)	p+=prime[j++];
			if(p==n) ans++,p-=prime[i++];
			else while(p>n) p-=prime[i++];
			if(p==n) ans++,p-=prime[i++];
			if(prime[j]>n) break;
		}
		printf("%d\n",ans);
	}
	return 0;
}

Dichotomy ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=10003;
int prime[N],cnt,s[N];
bool vis[N];
void init()// Preprocess out the prime prefix and  
{
	for(int i=2;i<=10000;i++)
	{
		if(vis[i]) continue;
		prime[++cnt]=i;
		for(int j=2;j*i<=10000;j++)
			vis[i*j]=true;
	}
	for(int i=1;i<=cnt;i++)
		s[i]=s[i-1]+prime[i];
}
bool check(int x,int rr)// see x Can it be regarded as No rr The continuous sum of primes at the end of primes  
{
	int l=0,r=rr-1,mid;
	while(l<r)
	{
		mid=l+r+1>>1;
		if(s[rr]-s[mid]>=x) l=mid;
		else r=mid-1;
	}
	if(s[rr]-s[l]==x) return true;
	return false;
}
int main()
{
	init();
	int n;
	while(1)
	{
		scanf("%d",&n);
		if(!n) break;
		int l=1,r=cnt,mid;
		while(l<r)// Find out if it is less than or equal to x The first prime of  
		{
			mid=l+r+1>>1;
			if(prime[mid]<=n) l=mid;
			else r=mid-1; 
		}
		int ans=0;
		for(int i=1;i<=r;i++)
			ans+=check(n,i);
		printf("%d\n",ans);
	}
	return 0;
}