プロジェクトオイラー＃10素数の合計

Question

私はプロジェクトオイラーのプロジェクト＃10で、2,000,000以下のすべての素数の合計を求める質問をしています。何らかの理由で、自分のコードを動作させることができません。私はどちらのデータ型を使うべきか理解していませんがint、long、longのどちらも機能していないようです。どんな助けやアドバイスも大歓迎です。ここに私のコードです。ありがとう。

int main(int argc, char *argv[]) 
{ 
int primes[100] = {2, 3, 5, 7}; 
//array of primes that have been found 
int fillcell = 4; 
//cell we are looking to fill 
int testnum = 8; 
//number being tested to see if it's a prime 
int divprime; 
int sum = 17; 
for(testnum = 8, fillcell = 4 ; testnum < 2000000 ; ++fillcell) 
{ 
    std::cout << "fillcell " << fillcell << std::endl; 
    for(; primes[fillcell] == 0 ; ++testnum) 
    { 
     std::cout << "testnum " << testnum << std::endl; 
     for(divprime = 0 ; testnum % primes[divprime] != 0 ; ++divprime) 
     { 
      std::cout << "divprime " << divprime << std::endl; 
      if(primes[divprime] >= sqrt(testnum)) 
      { 
       primes[fillcell] = testnum; 
       sum = sum + testnum; 
       std::cout << "prime found " << testnum << std::endl; 
       break; 
      } 
     } 
    } 
} 
std::cout << "sum" << sum << std::endl; 
} 

Answer 1

歩行の技術を学ぶ前に実行しようとしないでください。

int primes[100]のような固定サイズの配列は使用しない限り使用しないでください。 、nth Prime Pageに行くと、それはまた、あなたが必要です2000000

下記148933個の素数があることを見つけることによって、たとえば -

一つの理由は、これはあなたが、プログラマは、アップフロントに必要なサイズを決定するために必要なことです（あなたがJavaやC＃のようにあなたのためにこれを行う言語を使用していない限り）配列の境界を越えていないことを確認するコードに追加のチェックを追加することができます。さらにもう1つの理由は、ブックを保管するためのコードを追加する必要があるということです。つまり、アレイのセル数が現在占有されているかどうかを追跡する必要があります。

最後に、148933の整数の配列を自動変数（スタック上）に割り当てると、スタックをぶつけてクラッシュする可能性があります。

std::vector<>を使用すると、これらの頭痛はすぐに消え、コードははるかに簡単になります。

簡単な計画から始めて、ステップを別々のコードで実装します。すべてのコードにシンプルで明確な責任があれば、物事を踏襲するのが簡単です。あなたがすべてを1つの大きな悪い塊に絡ませると、状況はより困難になります。

たとえば、ベクトルで見つかった素数を保存しておけば、そこにある数字を見て、すべてがうまくいるかどうかを確認し、素数の既知のリスト（おそらくThe First 10,000 Primes、または素数最大1,000,000,000,000でprimos.mat.br）。見ることはできますが、そうする必要はありません。すべてを出力コードで散在させると、常にそれらすべてを見なければなりません。プログラムをデバッグして、それぞれのステップに従わない限り、合計に加算するだけでは見えません。

計画を擬似コードとして作成して、一目でその計画を理解し、完全に理解できるようにします。あなたが計画を持っていない場合、またはあなたがそれを理解していない場合、結果はcr * pになる可能性が非常に高いです。

for each candidate n between 2 and 2000000 
    for each known prime p up to sqrt(n) 
     if p divides n 
      break 
    if no divisor p was found // must be a new prime 
     add n to the list of found primes 

明らかに、「は除数Pが見つからなかった場合は、」基準は、内部ループの前にfalseに初期化されますdivisor_found、同様に、フラグを使用する必要があります。従って最初の改良：これは前置き

for each candidate n between 2 and 2000000 
    divisor_found := false 
    for each known prime p up to sqrt(n) 
     if p divides n 
      divisor_found := true 
      break 
    if not divisor_found // must be a new prime 
     add n to the list of found primes 

実現することができます。候補の列挙は、おそらく2の倍数のように、プライムすることはできませんいくつかの数字スキップすることによって改善することができる。

add 2 to the list of found primes 
for each odd number between 3 and 2000000 
    ... 

これをすぐに半分にワークロードを切断し、それが'wheel'の最も単純な例です。このような問題に対しては、3の倍数（mod 6車輪）を5で始まり、交互に2と4ずつ増やすことは非常に現実的です。ここで

add 2 and 3 to the list of found primes 
for n = 5 to 2000000 step 6 // 6 = 2 * 3 
    try n 
    try n + 2 

候補を列挙するあなたの方法は、すでにすべての倍数を除外しているため、tryで行わトライアル部門は、潜在的な除数として2または3を検討する必要はありません。 5の倍数をスキップする拡張もかなり簡単です。

最も内側のループが繰り返されるたびにsqrt(n)のような高価な計算を行うと、コードがクロールまで遅くなります。 nは内部ループの存続期間中は変化しませんので、不必要に計算を繰り返すのではなく、ループヘッダ内で値を1回計算してください。

異なる整数データ型をランダムに試してみると、あなたはどこにもいないでしょう。値が負になることができない場合は - unsignedを最初に選択してください。現在のシステムでは、これは通常uint32_tに対応しています。これは、このオイラーのタスクに関わる少数の小数点以下の処理に十分です。あなたは、適切なtypedefを導入することで、いくつかの手間を省くことができます。その方法は、あなただけ発生する必要があるの1つの定義を変更する必要があります。

typedef std::uint32_t num_t; 
typedef std::uint64_t sum_t; 
num_t const N = 2000000; 
... 

std::vector<num_t> primes; 
... 

for (num_t n = 3; n <= N; n += 2) 
    ... 

sum_t sum = 0; 
for (num_t p: primes) 
    sum += p; 

私も和の球場の推定がうまくuint32_tの容量を超えてそれを置くので、別のsum_tを追加しました。

いずれにしても、ここではSieve of Eratosthenesを真剣に検討する必要があります。ホイール式の試行分割よりも簡単で数桁も速く、最も簡単なレンダリングでも数百ミリ秒でこのオイラーの課題を解決するはずです。

Answer 2

DarthGizkaは、Sag of Eratosthenesを使用するようにアルゴリズムを変更することを含め、いくつかの良いアドバイスをしました。ここで私はあなたの選択した言語で書き換えることがあなたに残して私の解決策は、次のとおりです。

function sumPrimes(n) # sum of primes <= n 
    sum := 0 
    sieve := makeArray(2..n, True) 
    for p from 2 to n step 1 
     if sieve[p] 
      sum := sum + p 
      for i from p * p to n step p 
       sieve[i] := False 
    return sum 

Nがsieveアレイを形成するには大きすぎる場合は、セグメントに配列が必要になります。それを行う必要がある場合は、hereを参照してください。また、素数の総和を計算するルジャンドルの素数の計算方法のアルゴリズムでもありますが、非常に複雑です。