Atkin筛法在非常高的限制条件下出现故障

Question

我正在尝试解决欧拉计划问题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，但我无法弄清楚他们的代码与我的代码有何不同。

有人能看出我在这里做错了什么吗？

- user360907

Answer 1

您只有一个32位整数来表示答案。实际答案远大于32位整数所能表示的范围，因此您需要使用64位整数。尝试使用unsigned long long。

- Some programmer dude

---

两个答案之间的差异为141733920768，或者是0x2100000000。这8个末尾的零并非巧合。 - MSalters

Answer 2

你可以创建自己的类来存储大数。或者你可以使用整数数组来存储答案，并将每个数字存储在每个索引处。（即使无符号长长不起作用）:)

- user1362740