未知大小的动态数组

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++;
  }
}

- bratanKamil

---

使用 malloc 分配内存，然后使用 realloc 增加数组大小。 - Balu

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
    ...          ...

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

- Yu Hao

Answer 2

如果您能使用C++，您可以使用std::vector来解决您的问题。

- user1641854

---

如果你能够使用Python、Java或其他编程语言，那就太好了。 - glglgl

不一样。C是C++的子集，因此您可以自由地使用C++编译器编译C代码，并额外获得C++标准库。是的，我知道使用C++编译C代码会遇到一些问题。 - user1641854