运行时错误 (SIGSEGV) SPOJ 筛子的埃拉托色尼

Question

嗨，我遇到了这个问题的SIGSEGV错误，不知道问题在哪里：http://www.spoj.com/problems/PRIME1/我试图通过维基百科上给出的埃拉托色尼算法筛来解决它。这是我的代码，请提前帮助谢谢。

int main()
{
   int t;   // test cases
   cin>>t;
   while(t--)
   {
      long int m,n;
      cin>>m>>n;

      if( 1 <= m <= n <= 1000000000 && n-m<=100000)
      {
         bool a[n];
         for(long int i=2;i<=n;i++)
         {
            a[i]=true;  // set all to true
         }
         a[0]=false;
         a[1]=false;
         for( long int i=2;i*i<=n;i++)
         {
            if(a[i])
            {
               for( long int k=i*i;k<=n;k+=i)
               {
                  a[k]=false;
               }
            }
         }
         for(long int i=m;i<=n;i++)
         {
            if(a[i])
               cout<<i<<endl;         //Now all i such that a[i] is true are prime.
         }
         cout<<endl;
      }
      else
         return -1;
   }
   return 0;
}

Answer 1

你必须使用 gdb 来找出到底发生了什么。 这段代码有很多问题。

1. 正如评论中指出的，对于足够大的n，您的a[n]将溢出堆栈。

2. 您在第一个和第三个for循环中有一个逐个错误;您检查a[n]但最多只分配了a[n-1]。 所有i <= n都应该i < n

3. if( 1 <= m <= n <= 1000000000 && n-m<=100000)可能不是你想要的;对于任何正整数"n"，(1 <= m <=n)为真

Answer 2

在 10 的平方根以下有 3401 个素数⁹.这就是筛选低于 10⁹ 上限的任何数字段所需的全部内容。

因此，首先，从 2 到 31622 筛一段。将生成的 3401 个素整数存储在数组中。

然后，对于每对数字m <= n, m >= n - 100000创建一个临时数组，覆盖从m到n(含(的段，并用您在第一步中计算的素数将其筛选。当素数的正方形高于给定n时，您可以停止每次筛分：

for( i=0; primes[i]*primes[i] <= n; ++i)
{
    ....

另请参阅我关于埃拉托色尼"偏移筛"的帖子。

Answer 3

这个问题之前已经在 SO 上处理过。例如，请参阅堆栈溢出上的埃拉托色尼筛。您可能还想阅读此博客，其中描述了一个典型的 C 实现：埃拉托色尼筛子的 C 实现。如上所述，您的代码存在多个问题，实际上很多问题，您需要考虑完全重组它。请阅读链接的帖子以获取有关如何成功做到这一点的想法。