プロジェクトオイラー Problem 50 「連続する素数の和」 †

Problem 50 「連続する素数の和」 †

素数41は6つの連続する素数の和として表せる:

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

100未満の素数を連続する素数の和で表したときにこれが最長になる.

同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.

100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2050

解法
n個めからｍ個めまでの素数の和は
ｍ個めまでの素数の和-(ｎ-1)個めまでの素数の和です。
なのでｎ個めまでの素数の和を全部計算しておきます。
後は差分2１個以上というヒントを悪用して計算量を稼ぎます。



#include<stdio.h>
#include<vector>
#include<string.h>
#include<iostream>
#include <time.h>


const int LIMIT=1000000;
const int SUM_LIMIT=60000;
bool is_prime[LIMIT+1];

int main(){
      clock_t start,end;
      start = clock();
   
      int bigO=0;
   
      memset(is_prime,true,sizeof(is_prime));
      is_prime[0]=is_prime[1]=false;
      for(int i=2;i*i<=LIMIT;i++){
            if(is_prime[i]==false)continue;
            int start=4;
            int add=2;
            if(i%2==1){
                  start=i*i;
                  add=i*2;
            }
            for(int j=start;j<=LIMIT;j+=add){
                  bigO++;
                  is_prime[j]=false;
            }
      }
      std::vector<__int64> vec;
      __int64 sum=2;
      vec.push_back(0);
      vec.push_back(2);
      for(int i=3;i<SUM_LIMIT;i+=2){
            bigO++;
            if(is_prime[i]==false)continue;
            sum+=i;
            vec.push_back(sum);
      }
      __int64 sa;
      __int64 ansNum=0;
      int ansLen=0;
      for(int i=1;i<vec.size();i++){
            for(int j=i-ansLen;j>=0;j--){
                  sa=vec[i]-vec[j];
                  bigO++;
                  if(sa>LIMIT)break;
                  if(is_prime[(int)sa]==true){
                        ansLen=i-j;
                        ansNum=sa;
                  }
            }
      }
      end = clock();
       printf("%.2f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC);

      std::cout<<"bigO="<<bigO<<" sa="<<ansLen<<" ans="<<ansNum;
}