Sum of Consecutive Prime Numbers

NC228908. Sum of Consecutive Prime Numbers

描述

一些正整数可以用一个或多个连续素数的和来表示。给出一个正整数 $\ n$ ，有多少种不同的表示形式？

例如：

正整数53，有2种表示形式：5+7+11+13+17 和 53。

正整数41，有3种表示形式：2+3+5+7+11+13、11+13+17 和 41。

正整数3，只有1种表示，即 3。

正整数20，没有这种表示。注意被加数必须是连续的素数，因此 7+13 和 3+5+5+7 都不是正整数 20 的有效表示。

输入描述

第一行包含一个正整数。
接下来行，每行包括一个正整数。
数据保证。

输出描述

对于每组数据，输出一行，一个整数，表示答案。

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 487ms, 内存消耗: 49200K, 提交时间: 2022-06-25 12:23:54

#include<iostream>
using namespace std;
int prime[4000000],cnt,n;
bool ju[40000001];
int main()
{
	for(int i=2;i<=40000000;i++)
	{
		if(!ju[i])prime[++cnt]=i;
		for(int j=1;j<=cnt&&i*prime[j]<=40000000;j++)
		{
			ju[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		int ans=0;
		int l=1,sum=0;
		for(int i=1;i<=cnt;i++)
		{
			if(prime[i]>n)break;
			sum+=prime[i];
			while(sum>n)sum-=prime[l++];
			if(sum==n)ans++;	
		}
		cout<<ans<<endl;
	}
	return 0;
}