C initializing a (very) large integer array with values corresponding to index

Question

Edit3: Optimized by limiting the initialization of the array to only odd numbers. Thank you @Ronnie !

Edit2: Thank you all, seems as if there's nothing more I can do for this.

Edit: I know Python and Haskell are implemented in other languages and more or less perform the same operation I have bellow, and that the complied C code will beat them out any day. I'm just wondering if standard C (or any libraries) have built-in functions for doing this faster.

I'm implementing a prime sieve in C using Eratosthenes' algorithm and need to initialize an integer array of arbitrary size n from 0 to n. I know that in Python you could do:

integer_array = range(n)

and that's it. Or in Haskell:

integer_array = [1..n]

However, I can't seem to find an analogous method implemented in C. The solution I've come up with initializes the array and then iterates over it, assigning each value to the index at that point, but it feels incredibly inefficient.

int init_array()
{
    /* 
    * assigning upper_limit manually in function for now, will expand to take value for
    * upper_limit from the command line later.
    */
    int upper_limit = 100000000;
    int size = floor(upper_limit / 2) + 1;

    int *int_array = malloc(sizeof(int) * size);
    // debug macro, basically replaces assert(), disregard.    
    check(int_array != NULL, "Memory allocation error");

    int_array[0] = 0;
    int_array[1] = 2;

    int i;

    for(i = 2; i < size; i++) {
        int_array[i] = (i * 2) - 1;
    }

    // checking some arbitrary point in the array to make sure it assigned properly.
    // the value at any index 'i' should equal (i * 2) - 1 for i >= 2
    printf("%d\n", int_array[1000]);  // should equal 1999
    printf("%d\n", int_array[size-1]);  // should equal 99999999

    free(int_array);

    return 0;

error:
    return -1;
}

Is there a better way to do this? (no, apparently there's not!)

Answer 1

The solution I've come up with initializes the array and then iterates over it, assigning each value to the index at that point, but it feels incredibly inefficient.

You may be able to cut down on the number of lines of code, but I do not think this has anything to do with "efficiency".

While there is only one line of code in Haskell and Python, what happens under the hood is the same thing as your C code does (in the best case; it could perform much worse depending on how it is implemented).

There are standard library functions to fill an array with constant values (and they could conceivably perform better, although I would not bet on that), but this does not apply here.

Answer 2

Here a better algorithm is probably a better bet in terms of optimising the allocation:-

1. Halve the size int_array_ptr by taking advantage of the fact that you'll only need to test for odd numbers in the sieve
2. Run this through some wheel factorisation for numbers 3,5,7 to reduce the subsequent comparisons by 70%+

That should speed things up.