c - 在堆栈和堆上分配内存的埃拉托斯特尼筛法的内存错误

Question

我已经实现了以下版本的埃拉托斯特尼筛法，它在堆上分配内存来存储表示素数的数组。

void sieve(int *primes, int n) {
   for (int i = 0; i < n - 1; i++) {
      primes[i] = 1;
   }

   for (int p = 2; p <= n; p++) {
      if (primes[p - 2] == 1) {
         for (int i = 2*p - 2; i < n; i += p) {
            primes[i] = 0;
         }
      }
   }
}

void print_sieves(int n) {
   if (n < 3) return;

   int *primes = (int*) malloc((n - 1) * sizeof(int));
   sieve(primes, n);
   int print_counter = 0;

   for (int i = 0; i < n - 1; i++) {
      if (primes[i] == 1) {
         printf("%10d ", i + 2);
         print_counter++;

         if (print_counter % COLUMNS == 0)
            printf("\n");
      }
   }
   free(primes);
   printf("\n");
}

对于传递到 print_sieves 的大多数参数，程序按预期工作，但是，当将 15 传递到 print_sieves 时，我最终出现以下错误:

a.out: malloc.c:2392: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
Aborted (core dumped)

对于该程序的稍微不同的版本，我在堆栈上分配内存来存储表示素数的数组，我遇到了不同的错误。也就是说，当尝试查找太大的素数时，例如使用参数 10000000 调用 print_sieves 时，我遇到错误段错误(核心转储)。两个版本的程序的 sieve 实现是相同的，但 print_sieves 有细微差别。下面是我的 print_sieves 函数的代码，该函数在堆栈上分配内存:

void print_sieves(int n) {
   if (n < 3) return;

   int primes[n - 1];
   sieve(primes, n);
   int print_counter = 0;

   for (int i = 0; i < n - 1; i++) {
      if (primes[i] == 1) {
         printf("%10d ", i + 2);
         print_counter++;

         if (print_counter % COLUMNS == 0)
            printf("\n");
      }
   }
   printf("\n");
}

我的猜测是我没有正确管理内存，但我不知道哪里出了问题。是什么原因导致这些错误以及如何解决这些错误？

Answer 1

由于您为 n - 1 元素分配内存，我建议将 sieve() 中的最内层循环更改为

         for (int i = 2*p - 2; i < n; i += p) {

至

         for (int i = 2*p - 2; i < n - 1; i += p) {

为了使索引限制与分配的大小相匹配。

使用n = 10000000，您很可能会遇到堆栈溢出。

您可以使用getrlimit()/setrlimit()来获取/设置堆栈大小。从最大堆栈大小计算数组大小的限制可能很困难，因为您必须找出除了大数组之外还需要多少堆栈。

另请参阅Increase stack size in Linux with setrlimit