プロジェクトのオイラーを間違って出力する50

Question

プロジェクトオイラーの問題50を試しています。 （レベル2に近い：D）はこのように行く：、6つの連続素数の和として

素数41書くことができる。

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

これが最も長いです100を下回る素数に加算する連続素数の和。 素数を加えた1000未満の連続する素数の最長の和は、21項を含み、953に等しい。 最も連続する素数の合計として100万未満の素数はどれくらい書くことができますか？基本的にはそれだけで1000000までのすべての素数のベクトルを作成し、正しい答えを見つけるそれらをループ

#include <iostream> 
#include <vector> 
using namespace std; 

int main(){ 
    vector<int> primes(1000000,true); 
    primes[0]=false; 
    primes[1]=false; 
    for (int n=4;n<1000000;n+=2) 
     primes[n]=false; 
    for (int n=3;n<1000000;n+=2){ 
     if (primes[n]==true){ 
      for (int b=n*2;b<100000;b+=n) 
       primes[b]=false; 
     } 
    } 
    int basicmax,basiccount=1,currentcount,biggermax,biggercount=1,sum=0,basicstart,basicend,biggerstart,biggerend; 
    int limit=1000000; 
     for (int start=2;start<limit;start++){ 
      //cout<<start; 
      sum=0; 
      currentcount=0; 
      for (int basic=start;start<limit&&sum+basic<limit;basic++){ 
       if (primes[basic]==true){ 
        //cout<<basic<<endl; 
        sum+=basic;currentcount++;} 
        if (primes[sum]&&currentcount>basiccount&&sum<limit) 
         {basicmax=sum;basiccount=currentcount;basicstart=start;basicend=basic;} 

      } 
      if (basiccount>biggercount) 
       {biggercount=basiccount;biggermax=basicmax;biggerend=basicend;biggerstart=basicstart;} 
     } 
    cout<<biggercount<<endl<<biggermax<<endl; 
    return 0; 
} 

：

は、ここに私のコードです。答えは997651であり、カウントは543になるはずですが、私のプログラムはそれぞれ997661と546を出力します。何が間違っているのでしょうか？

Answer 1

それはあなたの素数のベクトルが間違っ

 for (int b=n*2;b<100000;b+=n) 
      primes[b]=false; 

を構築しているように私はそれが1,000,000ない10万されるべきだと思う見えます。それが一貫していることを確認する定数としてその数をリファクタリングする方が良いかもしれません。

それ以外の部分は基本的にはうまく見えますが、私たち自身でテストすることなく、ほかに何が追加できるのか分かりません。効率性を改善する余地は十分にあります。範囲を繰り返しスキャンするなど、多くの作業を行います。 prime[start]が偽であるときに合計が始まりません。加算などの素数の2番目のベクトルを作成できます（プロジェクトオイラーはランタイムとメモリの制限がありますか？覚えがたいですか）。

Answer 2

これについて間違った方法。

1. 合計が1,000,000未満となるように、素数の最大シーケンスを生成します。これは2、3、5、...、pです。いくつかのp。
2. このシーケンスを合計し、素数性をテストします。
3. プライムである場合は、終了して合計を返します。
4. 短いシーケンスは正しいシーケンスでなければなりません。順序を短くし、連続した素数のプロパティを保持するには、最初の要素を削除するか最後の要素を削除するという2つの方法があります。これらのシーケンスの両方で2から再帰します。