Problem 50 Consecutive prime sum （线性筛）

深藏阁楼爱情的钟 2022-07-15 03:22 152阅读 0赞

## 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?

<table> 
 <tbody> 
  <tr> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td> 
        <div style="text-align:right"> 
         <span style="font-size:18px">Answer:</span> 
        </div> </td> 
       <td><strong><span style="font-size:18px">997651</span></strong></td> 
      </tr> 
      <tr> 
       <td colspan="2"><span style="color:rgb(153,153,153)"><span style="font-size:18px">Completed on Mon, 31 Oct 2016, 10:49</span></span></td> 
      </tr> 
     </tbody> 
    </table> </td> 
  </tr> 
 </tbody> 
</table>

代码：

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