3

だから私はプロジェクトオイラーの問題50を試みています。（レベル2に非常に近い：D）次のようになります：

素数41は、6つの連続する素数の合計として記述できます。 

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

これは、100未満の素数に追加される、連続する素数の最長の合計です。1000未満の連続する素数の最長の合計は、素数に追加され、21の項を含み、953に等しくなります。100万未満のどの素数を最も連続する素数の合計として記述できますか？

これが私のコードです：

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

基本的には、1000000までのすべての素数のベクトルを作成し、それらをループして正しい答えを見つけます。答えは997651で、カウントは543であるはずですが、私のプログラムはそれぞれ997661と546を出力します。何が悪いのでしょうか？

4

2 に答える 2

2

素数ベクトルを間違って構築しているようです

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

それは10万ではなく1,000,000であるべきだと思います。その数値を定数としてリファクタリングして、全体で一貫していることを確認する方がよい場合があります。

残りの部分は基本的に問題ないように見えますが、自分でテストしないと、他に何を追加できるかわかりません。効率を改善する余地は十分にあります。範囲のスキャンを繰り返し実行します。たとえば、prime[start]falseの場合は合計を開始する意味がなく、合計の素数だけの2番目のベクトルを作成できます（プロジェクトオイラーにはランタイムがありますか）とメモリ制限の制限？思い出せない）

于 2012-04-18T16:21:55.203 に答える
0

あなたはこれについて間違った方法で考えています。

  1. 合計が1,000,000未満になるように、素数の最大シーケンスを生成します。これは2、3、5、...、pです。いくつかのpのために。
  2. このシーケンスを合計し、素数性をテストします。
  3. 素数の場合は終了し、合計を返します。
  4. 短いシーケンスが正しいシーケンスである必要があります。シーケンスを短縮し、連続する素数プロパティを保持するには、最初の要素を削除する方法と最後の要素を削除する方法の2つがあります。これらのシーケンスの両方で2から再帰します。
于 2012-04-18T16:29:01.587 に答える