在一维数组中动态存储质数

Question

我正在制作一个程序，将给定范围内的素数动态存储到一维数组中。我已经阅读了有关 c 中的动态内存分配的信息，但我不知道我的代码有什么问题。最初我定义了一个 "isprime" 函数来检查一个数是否是质数，如果这个数是质数它 returns 1。之后，我使用 for 循环帮助将素数存储在数组中。在 for 循环中，我使用了一个 if 语句来检查用户输入的范围内的数字是否为素数，如果是素数，则将其存储在数组 p 中，使用 malloc 为其动态分配内存。但是在数组 p 中没有存储素数，而是存储了垃圾值，我不知道为什么我的数组中没有存储素数？

#include<stdio.h>
#include<math.h>
int isprime(int n)
{
    int i;
    for(i=2;i<sqrt(n);i++)
    {
        if(n%i==0)
        {
            return 0;
        }
    }
    return 1;
}
main()
{
    int *p,i,n,j=1;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        if(isprime(i)&&i!=0&&i!=1)
        {
            p=malloc(j*sizeof(int));//Memory allocation for p should increase as more prime no.s are stored
            p[j-1]=i;
            j++;

        }
    }
    printf("%d\n",p[1]);//garbage value is printed instead of any prime no.
}

Answer 1

malloc 将在您的循环中每次 return 一个新的内存区域，从而丢失您以前的数据。

您需要 realloc 而不是

 int *p = NULL;  // initialize to NULL

在循环中：

        p=realloc(p,j*sizeof(int));

因此要么保留 p 地址并增加内存，要么复制来自 p 的先前数据并发布新的 p。无论哪种方式，它对您来说都是透明的。

（第一次，因为 p 是 NULL，它表现得像 malloc）

请注意，每次迭代时 realloc 的效率相当低。最好少调整大小，并记录容量和实际数据长度。比如像这样：

初始化：

  int growth = 100;
  int capacity = 0;
  int *p = NULL;

在循环中：

  if (j>=capacity)
  {
      capacity += growth;
      p = realloc(p,capacity*sizeof(int));
  }

另外：如评论所述，对于完整作业的答案，在检查素数时不要省略最后一个值，否则您会检测到完全正方形作为素数。

在一维数组中动态存储质数

dynamically storing prime numbers in a 1d array

c

memory

arrays

allocation

dynamic