1

所以这是素数筛的代码，它给出了正确的输出，完全符合我的要求，除了打印正确结果后出现的丑陋错误。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

void prime_gen(int *, int);
void show_primes(unsigned long, unsigned long, int *, int);

int main(void)
{
  int no_testcases=0;
  int count=0;
  unsigned long lower=0,upper=0;
  unsigned long size;

  size=sqrt(1000000000);
  printf("%lu\n", size);
  int * primes, *primes_temp;;
  primes=(int *)calloc(size+1,sizeof(int));
  assert (primes!=NULL);

  prime_gen(primes, size+1); /* generates array of 0 and 1's indicating if index is a prime number */

  scanf("%d", &no_testcases); /* no of test cases */
  while (count<no_testcases)
  {
    scanf("%lu %lu", &lower, &upper);
    show_primes(lower, upper, primes, size+1); /* shows all prime numbers in given range */
    count++;
    if (count!=no_testcases)
      putchar('\n');
  }

  free(primes);

  return 0;
}

和输出：

31622
size=31623, set_index=63248, index=31625
1
1
10  
2
3
5
7
No of primes = 4
*** glibc detected *** ./a.out: double free or corruption (out): 0x09d49008 ***
a.out: malloc.c:2451: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.
Przerwane (core dumped)

这是素数生成器和 show_primes 的代码：

void prime_gen(int * tab, int size) /* 0== is prime, 1== is not prime */
{
  tab[0]=1;
  tab[1]=1;
  unsigned long index=2;
  unsigned long set_index;


  for(index=2;index<=size;index++)
  {
    while (index<=size && tab[index]!=0) /* goes to next prime number */
    {
      index++;
    }
    for(set_index=index+index;set_index<=size;set_index+=index)
      tab[set_index]=1;
  }
  printf("size=%d, set_index=%lu, index=%lu\n", size, set_index, index);
}

void show_primes(unsigned long l, unsigned long u, int * array, int size)
{
  int index = 0;
  int is_prime=1;
  int primes_count=0;

  for(l;l<=u;l++)
  {
    if (l<=size) /* if l is valid index of array with primes */
    {
      if(array[l]==0)
      {
    printf("%lu\n", l);
    primes_count++;

      }
    }
    else /* if checked number is bigger than last index of array */
    {
      is_prime=1;
      for (index=2;index<=size;index++)
      {
    if (array[index]==0)
    {
      if (l%index==0)
      {
        is_prime=0;
        break;
      }
    }
      }
      if (is_prime)
      {
    printf("%lu\n", l);
    primes_count++;

      }
    }

  }
  printf("No of primes = %d\n", primes_count);
}

我将其缩小为 free(primes) 作为问题，因为当删除错误消失并且程序按预期终止时。而且我知道数组在这里会更好，但是动态数组对我来说是新的，这应该是我对它们的教训。非常感谢您的回答。

4

4 回答 4

1

在prime_gen功能上，你有这个：

for(set_index=index+index;set_index<=size;set_index+=index)
  tab[set_index]=1;

你正在溢出你的数组。在最后一次迭代中，您写入值大于tab[set_index]的元素。set_indexsize

尝试将for循环停止条件更改为：set_index < size

于 2013-08-26T21:27:46.120 回答
1

您正在调用数组primes_gen和数组的大小show_primes。primes在这些函数中，您正在读取和写入超出数组边界的函数：

for(set_index=index+index;set_index<=size;set_index+=index)
  tab[set_index] = 1;

这正在破坏您的阵列，因此您的调用free()失败。

于 2013-08-26T21:28:41.347 回答
1

我猜：

void prime_gen(int *, int);
void show_primes(unsigned long, unsigned long, int *, int);

int main(void)
{
  int no_testcases=0;
  int count=0;
  unsigned long lower=0,upper=0;
  unsigned long size;

  size=sqrt(1000000000);
  printf("%lu\n", size);
  int * primes, *primes_temp; *primes_head;
  primes=(int *)calloc(size+1,sizeof(int));
  primes_head = primes;
  assert (primes!=NULL);

  /* NOTE CHANGE BELOW */
  prime_gen(primes, size); /* generates array of 0 and 1's indicating if index is a prime number */

  scanf("%d", &no_testcases); /* no of test cases */
  while (count<no_testcases)
  {
    scanf("%lu %lu", &lower, &upper);
    /* NOTE CHANGE HERE */
    show_primes(lower, upper, primes, size); /* shows all prime numbers in given range */
    count++;
    if (count!=no_testcases)
      putchar('\n');
  }

  free(primes_head);

  return 0;
}
于 2013-08-26T21:15:21.807 回答
0

尝试移出scanf("%lu %lu", &lower, &upper);循环

于 2013-08-26T21:26:10.017 回答