Extending Sieve of Eratosthenes beyond a billion
A few things you can do:


Use a bit vector (with bit manipulation) instead of a bool array. This gives you 8 times more memory. If you use C++ vector&lt; bool&gt; you get this optimization for free.
Store only odd numbers in the array. This will save additional factor of 2 in memory. You need to adapt the logic of the program a little bit, but this is not extremely difficult. This saves also some time because in the first iteration the algorithms just marks half of the numbers.
The outer loop (the while (i &lt; MAX)) only needs to run from 0 to ceil(sqrt(MAX)).
The inner loop can start at i*i not just 2*i.


Summarizing the first two will give you factor of 16 more memory (or factor of 16 more numbers to sieve with given memory) and the last two will significantly improve the run-time (not sure by how much exactly).

The segfault is most likely due to the fact that a == NULL, i.e. the malloc routine fails to allocate the memory. You need to check for NULL after the malloc call and before memset.