Extending Sieve of Eratosthenes beyond a billion

For MAX value of 1000000000 (\$10^9\$), it takes about 45 seconds to reach the line where it prints "done". How can I speed this up?

Is printing to screen always going to take so much time? I know it's hardware.

On increasing the size of MAX beyond \$10^9\$ gives me an exception on the line memset(a, true, MAX);. Is there any limit to this function? I should be able to use all of the RAM. Running this program uses around 954 MB of memory.

void sieve_of_eratosthenes(){
    bool* a;
    a = (bool*)malloc(MAX * sizeof(bool));
    memset(a, true, MAX);
    unsigned long int i = 1;
    while (i = MAX)
            break;

        for (unsigned long int k = 2 * i; k < MAX; k += i)
            if (a[k])
                a[k] = false;
    }
    std::cout << "done\n";
    for (unsigned long int i = 2; i < MAX; i++)
        if (a[i])
            std::cout << i << "\n";
    getchar(); getchar();
}

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

-
The inner loop can start at ii not just 2i.

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

StackExchange Code Review Q#114485, answer score: 28