Sieve of Eratosthenes optimization I have applied some optimizations like storing only odd values
and starting to mark off from square of the number.

Can it be optimized further?

bool * isPrime = new bool [n/2];

for (int i=0; i &lt; n/2; ++i)
    isPrime [i] = true;

cout&lt;&lt; 2 &lt;&lt; "\n";

for (int i = 3; i &lt; n; i += 2) {

    if (isPrime [i / 2]) {

        cout&lt;&lt; i &lt;&lt; "\n";

        for (int j = i * i; j &lt; n; j += 2 * i)
            isPrime [j / 2] = false; 
    }
}
You can go further by not processing multiples of 3 together with multiples of 2 (even numbers, which you already not process). For stepping on numbers not multiple of 2 and 3, you should take steps of size 2 and 4 alternatively. 5 (+2) 7 (+4) 11 (+2) 13 (+4) 17 ...

This way you will also save space (from n/2 to n/3). You can change your loops like below:

for (int i = 5, t = 2; i &lt; n; i += t, t = 6 - t) {

    if (isPrime [i / 3]) {

        cout&lt;&lt; i &lt;&lt; "\n";

        for (int j = i * i, v = t; j &lt; n; j += v * i, v = 6 - v)
            isPrime [j / 3] = false; 
    }
}


a little hint is that if don't want to print the prime numbers and want just to generate isPrime array, you can change your outer loop condition to i*i&lt;n, because composite numbers are turned to false by their factor less than their square root.

Another good optimization is that you can use a single bit for storing isPrime flag of each number. This way you can save space by a factor of 1/8, and what is great about this method is that you are increasing your locality of reference and your code will use cache better (when I first wrote sieve by this optimization, amazingly I achieved about 20% speed improvement).