连续素数和题解

· · 题解

题目名称：连续素数之和

所用算法：欧筛 + 双指针

为了代码的严谨性，我们尽量避免打表。

主要思路：

首先先用优化的欧几里得算法来找出所有的质数，虽然可以打表，但不建议，因为最好像这种题练习筛选质数。

接着因为这道题是不固定数量输入的，所以我们要用 while 循环输入，因为题目说输到是 0 为止，还有一个要满足的条件就是输入的变量不为 0。

接着就是双指针了，我们在 for 循环里定义两个变量 i,j，表示在 [i,j] 的区间内找。

首先先特判质数本身不能已经比总和大，如果是，把直接退出循环了，接着就是定义一个小的 sum 要加上左指针指的质数，质数小到大排列后用 while 移动右指针直到 sum\ge 总和并且 j<i 的条件不满足，然后再看 sum 和 n 相不相等，相等就继续加，重复即可，最后输出答案即可。

至于双指针为什么这么做因为如果 sum<n 的时候，由于质数按从大到小的顺序存的，所以右边界向前，左边界不变，相反情况大于，左边界向前，右边界不动要把前面的上次左边界的数删了，当然左右边界在同一个位置也是存在的。

参考代码：


#include<bits/stdc++.h>
using namespace std;
const int N=400000;//为了即使数据量大，也使用方便，也可以写作define N 400000
int prime[N+5],cnt;//记录质数的数组多开防越界
bool is_prime[N+5];//判断质数出现的函数
void get_prime(){//欧筛函数
    for(int i=2;i<=N;i++){
        is_prime[i] = 1;
    }
    for(int i=2;i<=N;i++){
        if(is_prime[i] == 1){
            prime[++cnt] = i;
        }
        for(int j=1;j<=cnt&&prime[j] * i<=N;j++){
            is_prime[prime[j]*i] = 0;
            if(i%prime[j] == 0){
                break;
            }
        }
    }
    return;
}
int n,m;
int main(){
    get_prime();
    while(cin>>n){
    if(n==0){
        return 0;
    }
        int sum = 0,ans = 0;//初始化sum为质数总和，ans为总和为n的方案数
        for(int i=1,j=1;i<=cnt;i++){//双指针
            if(prime[j] > n){//如果质数原本就比总和大，直接break跳出循环
                break;
            }
            sum=sum+prime[i];//左指针
            while(sum>n&&j<i){
                sum=sum-prime[j];//右指针
                j++;//右指针移位
            }
            if(sum == n){//如果相等那么方案数加1
                ans++;
            }
        }
        cout<<ans<<'\n';//输出，别忘换行
    }
    return 0;
}
``