最强素数【区间长度】

题目描述

小李在你帮助之下轻松战胜了他的同学们，于是满怀恶意的同学出了一个题目来为难小李，作为小李神一样的队友，你又要出力了。
素数41能写成连续6个素数之和：41=2+3+5+7+11+13。
现在要求n以内的素数中，能表示为最多连续素数之和的那个数，如果有多个答案，请输出最大的那个素数。

输入

仅一行，一个整数n（1<=n<=1000000）。

输出

输出就一个整数，为所求的能表示为最多连续素数和的那个素数。

分析：

1.首先不要理解错题意，我就理解错了，我以为都是从2开始加，后来发现可能后面的加起来的等于的数要大而且要多。

2.根据这个题目来言，首先要进行素数打表，不然之后挨个判断是否为素数过于麻烦。

3.题目要求输出最大的那个素数。

思路：

我们可以先从2开始把之后的素数都加一遍，直到他大于n就结束，在这之前保留最大的那个素数。然后在从3开始，直到和大于n结束，这样以此枚举。然而问题是，怎么找到素数最多的那个而且又是最大的数，我们可以用区间长度，来表示，例如从2开始加到 这就 3-2+1=2，所以这中间有两个素数，如果以后枚举过程中，遇到区间长度一样的，应该输出后来的数，因为要输出最大的素数（肯定越往后加，和越大），具体实现代码如下：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
int vis[(int)(1e6+5)];
int prime[(int)(1e6+5)];
int main(){

    int cnt=0;
    for(int i=2;i<=1e6;i++)
        if(!vis[i])
        {
            prime[++cnt]=i;
            for(int k=2*i;k<=1e6;k+=i)
                vis[k]=1;
        }
    int sum=0;
    int num=0;
    int m,n,x;
    scanf("%d",&n); 
    for(int i=1;i<=cnt&&prime[i]<=n;i++)
    {
        sum=0;
        for(int k=i;k<=cnt;k++)
        {
            sum+=prime[k];
            if(sum<=n&&!vis[sum])
            {
                num1=k-i+1;//k-i+1表示区间长度
                x=sum;
            }
            if(sum>n）
                break;
        }
        if(num1>=num)//每次找到符合要求的数比较一下区间长度，也就是之前的素数个数
        {
            m=x;//最大值更新
            num=num1;//区间长度更新
        }
    }
    printf("%d",m);
    return 0;
}

附加一个简略代码：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
int vis[(int)(1e6+5)];
int prime[(int)(1e6+5)],num[500000];
int main(){
 
    int cnt=0;
    for(int i=2;i<=1e6;i++)
        if(!vis[i])
        {
            prime[++cnt]=i;
            for(int k=2*i;k<=1e6;k+=i)
                vis[k]=1;
        }
 
    int n;
    scanf("%d",&n);
 
    int num=0,ans=0;//zui chang
    for(int x=1;x<=cnt&&prime[x]<=n;x++)
    {
        int sum=0;
        for(int i=x;i<=cnt;i++)
        {
            sum+=prime[i];
            if(!vis[sum]&&sum<=n)
            {
                if(i-x+1>=num) ans=max(ans,sum),num=i-x+1;
            }
            if(sum>n) break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

思想是一样的，更为简单而已。

简单代码，有错指正。