プロジェクトオイラー数10＃

Question

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. 

Find the sum of all the primes below two million. 

そして、私の答えは：なぜこれが動作しない

bool IsRishoni; 
int soap = 0; 
for (int i = 3; i < 2000000; i++) 
{ 
    IsRishoni = true; 
    for (int a = 2; (a <= Math.Sqrt(i)) && (IsRishoni); a++) 
    { 
     if (i % a == 0) 
      IsRishoni = false; 
    } 
    if (IsRishoni) 
    { 
     soap = i + soap; 
    } 
} 
Console.WriteLine(soap + 2); 
Console.ReadLine(); 

？私が得た答えは1179908154 ...助けてください。

Answer 1

soap = checked(i + soap); 

で

soap = i + soap; 

を交換し、問題が露出しなければならない..and。

この質問は、より多くの詳細を持っている：あなたは32ビット符号付き整数（int）を通じて表現するには大きすぎるかもしれません後にしているNo overflow exception for int in C#?

Answer 2

あなたの答え（soapに格納されています）はint.Maxvalue（2,147,483,647）より大きい値です。

あなたの答えは、あなたがそれよりも大きいデータ型を使用する必要があるつまり〜1500億

です。

long.MaxValue = 9,223,372,036,854,775,807 
int.Maxvalue = 2,147,483,647 

Answer 3

結果。

てみましょう最初の結果の上位すべて数字が素数であることを仮定することにより拘束を決定します。 summationを通じて、N（含む）までの数字の合計がN * (N + 1)/2であることがわかりました。したがって、2,000,000までのすべての素数の合計の上限は2000,001,000,000です。これは、int,2,147,483,647の最大値よりも大きいので、数値オーバーフローが発生している可能性があります。これは暗黙のうちに無視されます。

あなたがあなたの答えのより正確な推定を望んでいた場合は、0とN間のランダムな整数が素数である確率は約1/ln(N)であると述べている、prime number theoremを使用することができます。これを以前の公式と組み合わせると、Nまでのすべての素数のおおよその合計はN * (N + 1)/(2 * ln(N))になります。 2,000,000の場合、これは約138,000,000,000と評価され、それはまだintの最大値よりも大きい。

問題を解決するには、soap変数に使用している整数データ型を、longなどの64ビット整数表現に簡単に切り替えることができます。その最大値は9,223,372,036,854,775,807なので、あなたの番号を明らかに表すことができます。別のノートで

long soap = 0; 

：あなたは系列の素数ので作業しているので、あなたの実装がSieve of Eratosthenesに変更した場合、あなたは巨大なパフォーマンスの向上（少なくとも100倍）を達成できます。