dynamic array with unknown size

Question

I want to write a program in C where the user types in 2 numbers a and b.

0 < a < INT_MAX

a < b < INT_MAX

The program checks how many Prime numbers are in between a and b and saves all of them in a dynamic array.

For the malloc function I need the size of the array, which means I have to first check all numbers if they are prim numbers just to get the size of the array, then use malloc(), and then check all numbers again to fill the array. Is there any possibility to make this run faster and not doing the same thing twice?

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

Since the size is unknown in the beginning, allocating the space for the size of one more element is inefficient.

One possible solution is: reallocate the space(Use realloc) twice the size of the previous size whenever the size is not enough.

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

This way, the times of reallocation is not much, and you don't waste much space.

Answer 2

If you are able to use c++ - you can use std::vector which solves your problem.