c - 大小未知的动态数组

Question

我想用 C 语言编写一个程序，让用户输入 2 个数字 a 和 b。

0 < a < INT_MAX

a < b < INT_MAX

程序检查 a 和 b 之间有多少素数，并将它们全部保存在动态数组中。

对于 malloc 函数，我需要数组的大小，这意味着我必须首先检查所有数字是否为原始数字，才能获得数组的大小，然后使用 malloc()，然后再次检查所有数字以填充数组。有没有可能让这个运行得更快而不是重复做同样的事情？

for (int i = a; i <= b; i++)
{
  if (check_if_prime(i) == 0)
    size++;
}
primze_numbers = malloc(size*sizeof(int));
int j = 0;
for (int i = a; i <= b; i++)
{
  if(check_if_prime(i) == 0)
  {
    prime_numbers[j] = i;
    j++;
  }
}

Answer 1

由于一开始大小是未知的，为多一个元素的大小分配空间是低效的。

一个可能的解决方案是:当大小不够时，重新分配空间(使用 realloc)两倍于之前的大小。

Real size - Space size
    0            0
    1            1
    2            2
    3            4
    4            4
    5            8
    6            8
    7            8
    8            8
    9            16
    10           16
    ...          ...

这样，重新分配的次数不多，也不会浪费太多空间。