-4

嗨，我收到此问题的 SIGSEGV 错误，不知道问题出在哪里： http ://www.spoj.com/problems/PRIME1/ 我试图通过 Wikipedia 上给出的 sieve-of-Eratosthenes 算法来解决它。这是我的代码，请帮助提前谢谢。

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;
}
4

3 回答 3

4

你必须使用 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)将是真的

于 2013-05-27T22:08:11.973 回答
2

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

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

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

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

另请参阅我关于 Eratosthenes 的“偏移筛”的帖子。

于 2013-05-28T07:40:30.240 回答
0

这个问题之前已经在 SO 上处理过。例如，请参阅Stack Overflow 上的埃拉托色尼筛。您可能还想阅读这篇描述典型 C 实现的博客：Eratosthenes Sieve 的 C 实现。如上所述，您的代码存在多个问题，实际上您需要考虑完全重新组织它。请阅读链接的帖子以获取有关如何成功执行此操作的想法。

于 2013-05-28T00:37:39.450 回答