时间戳

首页 > 解决方案 > 分段错误（核心转储）在 Eratosthenes 的筛子上尝试非常大的数字

c++ - 分段错误（核心转储）在 Eratosthenes 的筛子上尝试非常大的数字

问题描述

我必须找出小于给定 N 的数字有多少是素数，N <= 5 * 10 ^ 7 我试图声明数字long long, int long，并且我收到非常高的值的分段错误错误。
代码是：

#include <bits/stdc++.h>
using namespace std;

long  long int counter;
void SieveOfEratosthenes(long long int n)
{
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));

    for (long long  int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
            for (long long  int i = p * p; i <= n; i += p)
                prime[i] = false;
    }
    for (long long  int p = 2; p <= n; p++)
        if (prime[p])
            counter++;
    cout << counter;
}
int main()
{
    long long int n;
    cin >> n;
    SieveOfEratosthenes(n);
    return 0;
}

标签： c++

解决方案

正如我所怀疑的，根据我的 gdb，段错误发生在memset（测试 N = 10000000）：

Program received signal SIGSEGV, Segmentation fault.
0x0000555555554999 in SieveOfEratosthenes (n=10000000) at soe.cpp:8
8       memset(prime, true, sizeof(prime));

这是在数组初始化之后立即执行的，因此实际上是“开箱即用”。问题是您在堆栈上声明了一个巨大的数组，并且那里没有足够的内存。你的内存用完了。

要访问计算机的其余内存，您需要在堆上创建一个数组。在大多数情况下，最好的方法是使用标准 C++ 库类std::vector。声明后，它就像一个数组一样有效地工作，但它会为你做内存管理。您也可以使用mallocor更“直接”地做到这一点new，但是您必须自己管理内存（特别是，您需要freeordelete完成后，在函数返回之前，因为如果你不这样做，你会得到一个“内存泄漏”：至少只要程序正在运行，就会有一块内存在附近，可能非常大，直到您的操作系统在程序停止后回收它之前，什么都做不了，因为您丢失了指向它的指针。虽然在这里可能不是问题，但您不希望在更严重的应用程序中发生这种情况。）。

当然，一旦达到计算机内存的绝对限制，程序最终还是会失败，因此您应该包括进一步的处理代码（特别是检查 malloc 或 new 返回的指针是否为 NULL，或者是否使用 std::向量，使用 try/catch 中std::bad_alloc代码周围的 [IIRC] 异常SieveOfEratosthenes来优雅地处理这种情况（例如，显示“没有足够的内存来执行这么大的运行”消息）。

ADD：将所有这些更改放在一起，它应该看起来像

//#include <bits/stdc++.h> don't use this include. Can be very harmful
// if you aren't careful. And can be very harmful even then.
#include <iostream> // list all of the headers you need
#include <vector>
#include <algorithm> // for std::fill, see below

using namespace std; // fyi. generally not good practice to use
                     // "using namespace std" lest it become a habit
                     // (e.g. what if you make another function called "fill"
                     //  below?)

long long int counter; // fyi 2. does not need to be global

void SieveOfEratosthenes(long long int n)
{
    try {
      vector<bool> prime(n + 1);
      fill(prime.begin(), prime.end(), true); // has same fx as memset.
      // could also use
      // vector<bool> prime(n + 1, true);
      // to allocate and fill at the same time.

      for (long long  int p = 2; p * p <= n; p++)
      {
          if (prime[p] == true)
              for (long long  int i = p * p; i <= n; i += p)
                  prime[i] = false;
      }
      for (long long  int p = 2; p <= n; p++)
          if (prime[p])
              counter++;
      cout << counter << endl; // "endl" to give a newline to make it nice
    } catch(const std::bad_alloc &) { // prefer to catch by constant 
                                      // reference
      cout << "Sorry, not enough memory to do a run that large." << endl;
    }
}

int main()
{
    long long int n;
    cin >> n;
    SieveOfEratosthenes(n);
    return 0;
}

推荐阅读