Problem 50 Consecutive prime sum （线性筛）-蒲公英云

Problem 50 Consecutive prime sum （线性筛）

Consecutive prime sum

Problem 50

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Answer:	997651
Completed on Mon, 31 Oct 2016, 10:49

代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> primes;
int prime[1000000];
void init()
{    
    for(int i = 0 ; i < 1000000 ; i++){
        prime[i] = 1;   
    }
    for(int i = 2 ; i < 1000000; i++)
    {
        if (prime[i])
        {
            primes.push_back(i);
            if(i <= (int)sqrt((double)1000000))
            {    
                for(int t = i*i ; t<1000000 ; t+=i)//prime[i*i+k*i]=false
                {   
                    prime[t] = 0;
                }
            }
        }
    }
}
int main()
{    
    init();
    int max = 0;
    int maxlen = 0, maxsum = 0, cursum = 0;
    for(int i = 2 ; i < primes.size() ; i++)
    {
        cursum = 0;
        for(int j = i ; j < primes.size() ; j++)
        {
            cursum+=primes[j];
            if (cursum>=1000000)  break;
            if (prime[cursum] && j - i > maxlen )
            {
                maxlen = j-i;
                maxsum = cursum;
            }
        }
    }
    cout<<maxsum<<endl;;
    return 0;
}