我是靠谱客的博主 怕孤独画笔,这篇文章主要介绍Sum of Consecutive Prime Numbers题意:思路:,现在分享给大家,希望可以做个参考。

传送门

题意:

给你一个数n,将这个数表示成一段连续素数的和,问你有多少种表示形式。

思路:

欧拉筛筛出4e7之前的素数,再用双指针维护区间和。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int cnt;
int vis[40000010];
int pri[10000010];
ll sum[10000010];

void oula()
{
	for(int i = 2; i <= 40000000; i++)
	{
		if(!vis[i])pri[++cnt] = i;
		for(int j = 1; j <= cnt && pri[j]*i <= 40000000; j++)
		{
			vis[i*pri[j]] = 1;
			if(i%pri[j] == 0)break;
		}
	}
}

int main()
{
	oula();
	for(int i = 1; i <= cnt; i++)sum[i] = sum[i-1]+pri[i];
	int t;
	cin>>t;
	while(t--)
	{
		ll n;
		cin>>n;
		int ans = 0;
		for(int i = 1,j = 0; i <= cnt && pri[i] <= n; i++)
		{
			while(sum[i]-sum[j] > n)j++;
			if(sum[i]-sum[j] == n)j++,ans++;
		}
		cout<<ans<<endl;
	}
}

最后

以上就是怕孤独画笔最近收集整理的关于Sum of Consecutive Prime Numbers题意:思路:的全部内容,更多相关Sum内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(61)

评论列表共有 0 条评论

立即
投稿
返回
顶部