问题 D: 连续质数和

时间限制: 1.000 Sec  内存限制: 128 M

题目描述

质数又称素数，是大于 1 的正整数，除了 1 和它本身外不能被其他自然数整除，有无限 个，比如，2、3、5、7 等都是质数，但比如 9 就不是质数，因为它除了能被 1 和它自己整 除外，还能被 3 整除。 
悦悦小朋友对这类质数非常感兴趣，因为他发现有一些数是能通过连续的质数相加得 到的。比如 5+ 7 + 11 + 13 + 17=53，也就是整数 53 可以由连续的质数 5、7、11、13、17 相 加得到。有时相加的方案还不止一种，比如整数 41  就有 3  种不同的连续质数相加方案： 
2+3+5+7+11+13=41，11+13+17=41，还有一种就它本身，即 41=41。但也有的数是没有这样 
相加方案的，比如整数 20 就找不到连续质数相加的方案，虽然 7 + 13 或者 3 + 5 + 5 + 7 的 结果都是 20，但前者没有连续，后者质数被重复相加了 。悦悦在纸上写了 N（1≤N≤100000） 个数，他想知道每一个整数 Mi（2≤Mi≤100000，1≤i≤N）到底有多少种连续质数相加的 方案？请你编程帮助他一下吧。 

输入

输入共 N+1 行。 第 1 行一个整数 N，表示悦悦在纸上写了 N 个整数。 
接下来每行一个整数，其中第 i+1 行表示整数 Mi 

输出

输出共 N 行。 输出的第 i 行表示整数 Mi 有多少种连续质数相加的方案。 

样例输入 

4
2
12
17
20

样例输出

1
1
2
0

提示

样例中悦悦写了4个整数，分别为2，12，17和20。因为2=2，所以2可以找到满足条件的1种方案。
因为5+7=12，所以12有1种方案。
因为2+3+5+7=17，17=17，所以17有2种方案满足条件。
20没有满足条件的方案，所以输出0。

对于30%的数据保证1≤N≤100，2≤Mi≤100。对于50%的数据保证1≤N≤1000，2≤Mi≤1000。
对于100%的数据保证1≤N≤100000，2≤Mi≤100000。

想法：

其实.....好像问题并不是很困难，先用素数筛筛选出1000000以内的素数，然后利用前缀和来计算连续素数和就可以过啦。

但是好多人都时间超限了......这道题在代码实现的过程中要十分注意优化...

让我们来看代码吧？

#include <cstdio>
#define MX 1e9
#define MN -1e9
typedef long long int ll;
using namespace std;
int pri[10000];
int bet[10000];
bool isp[100010];
ll cnt;
inline ll solve(ll tar){           //这是求解过程
    ll i=0,j=0,tol=0;              //其实不用写成函数，直接复制下去就可以。
    do{                        
        j++;
        while(bet[j]-bet[i]>tar)      //这里只用了一层循环，比两层循环的会快一些！
            i++;                      //很多求子列的问题都可以用一层循环完成。
        if(bet[j]-bet[i]==tar)        //那些的问题的共同特点是：
            tol++;                    //如果当前子列不满足条件，相同起点的所有子列都不会满足。
    }while(j>i);                      //也就是说...子列必须是有序的？。
    return tol;                    
}
int main(){
    ll i,j,n,tar;
    bet[cnt]+=pri[cnt];
    for(i=2;i<=100010;i++){               //用埃氏筛筛选素数
        if(isp[i])
            continue;
        pri[++cnt]=i;
        bet[cnt]=pri[cnt]+bet[cnt-1];
        for(j=i;j*i<=100010;j++){
            isp[j*i]= true;
        }
    }
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&tar);
        printf("%lld\n",solve(tar));
    }
}

我把1也作为素数加进去了......结果错麻了，WA了一整晚.. : (