天天看點

Sum of Consecutive Prime Numbers

​​傳送門​​

Sum of Consecutive Prime Numbers

題意:

思路:

#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;
  }
}      

繼續閱讀