时间戳

首页 > 解决方案 > 在堆栈和堆上分配内存的 Eratosthenes 筛的内存错误

c - 在堆栈和堆上分配内存的 Eratosthenes 筛的内存错误

问题描述

我已经实现了以下版本的 Eratosthenes 筛子，它在堆上分配内存来存储表示素数的数组。

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)

对于这个程序的一个稍微不同的版本，我在堆栈上分配内存来存储表示素数的数组，我遇到了一个不同的错误。也就是说，当试图找到太大的素数时，例如在print_sieves使用参数调用时10000000，我遇到了错误Segmentation fault (core dumped)。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");
}

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

标签： cmemory-managementsieve-of-eratosthenes

解决方案

由于您为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()来获取/设置堆栈大小。从最大堆栈大小计算数组大小的限制可能很困难，因为您必须找出除了大数组之外还需要多少堆栈。

另请参阅使用 setrlimit 在 Linux 中增加堆栈大小

推荐阅读