3

ユーザーが200万未満のすべての素数の合計を計算するように求められるプロジェクトオイラー問題10を解決しようとしています。ウィキペディアで疑似コードを調べて次のように書きましたが、入力しようとすると、少なくともウェブサイトによると、生成される答えは正しくないようです。

int main()
{
   int limit = 2000000;
   int answer = 5;

   std::vector<bool> isPrime;
   for( int i = 0; i < limit; ++i ){
      isPrime.push_back( false );
   }

   int n = 0;
   for( int x = 1; x <= ceil( sqrt( limit ) ); ++x ){
      for( int y = 1; y <= ceil( sqrt( limit ) ); ++y ){

         n = 4*x*x + y*y;
         if( (n <= limit) && ( n%12 == 1 || n%12 == 5 ) ){
            isPrime.at(n) = ! isPrime.at(n);
         }

         n = 3*x*x + y*y;
         if( (n <= limit) && ( n%12 == 7 ) ){
            isPrime.at(n) = ! isPrime.at(n);
         }

         n = 3*x*x - y*y;
         if( (x > y) && (n <= limit) && (n%12 == 11) ){
            isPrime.at(n) = ! isPrime.at(n);
         }
      }
   }

   for( n = 6; n <= ceil( sqrt( limit ) ); n += 2 ){
      if( isPrime.at(n) ){
         for( int m = n*n; m < limit; m += n*n ){
            isPrime.at(m) = false;
         }
      }
   }

   for( int i = 5; i < limit; i += 2 ){
      if( isPrime.at(i) ){
         answer += i;
      }
   }

   std::cout << "The sum of the primes below " << limit << " is " << answer << std::endl;

   return 0;
}

次の出力が生成されます。

The sum of all the primes below 2000000 is 1179908154

手で確認できる小さな制限でテストしましたが、コードは実際にそれらの数値に対して正しく機能しています。答えが であるべきであることを示す他の人々の実装を見つけまし142913828922たが、彼らのコードが私のコードとどこが違うのかわかりません。

ここで私が間違っていることを誰かが見ることができますか?

4

2 に答える 2

8

答えには、符号付きの32ビット整数しかありません。実際の答えは32ビットに収まるよりもはるかに高いため、64ビット整数の使用に取り掛かる必要があります。unsigned long long代わりに使用してみてください。

于 2012-06-14T11:10:40.413 に答える
-1

独自のクラスを作成して大きな数字を格納することもできます。または、整数の配列を使用して答えを格納し、各インデックスに各桁を格納することもできます。(unsigned long long が機能しない場合でも) :)

于 2012-06-14T11:15:50.377 に答える