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 < n/2; ++i)
isPrime [i] = true;

cout<< 2 << "\n";

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

if (isPrime [i / 2]) {

cout<< i << "\n";

for (int j = i * i; j < n; j += 2 * i)
isPrime [j / 2] = false;
}
}

• You can get less memory usage (one bit per bool) by using std::vector<bool>. Possibly downside, indexing is a bit harder. But in any case a vector<char> would be better over dynamically allocating an array of bools. – UncleBens Jan 1 '12 at 13:10
• why is vector better than array of bools..what is the need for dynamic array like vector – Sumit Jain Jan 2 '12 at 15:20
• Because the C++ language says vector<bool> is specialized to only use one bit per bool. That is probably the worst idea in the standard, if you ask me - it means a[0] cannot be a bool&. – Christopher Creutzig Mar 6 '13 at 21:58
• It's always good to test a hypothesis regarding the relative performance of code in C++. – Edward Dec 21 '16 at 16:54

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 < n; i += t, t = 6 - t) {

if (isPrime [i / 3]) {

cout<< i << "\n";

for (int j = i * i, v = t; j < 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<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).

• I guess a link to the wheel factorization which is looks like this algorithm comes from might be handy. You can go further and make wheel bigger than 6, but you'll have to store your sectors sequence in a general form rather than +2, +4, +2.... – ony Jan 7 '13 at 9:38

Before starting to optimize, a few questions to be asked :

• does you code compile ? (I find the way you use isPrime pretty weird)
• is your code working properly ? (I think the initialization of isPrime with "false" is wrong)

And then, once you have a yes for the 2 previous questions, you can ask yourself :

• why do I want to optimize ?
• what do I want to optimize ?

And finally, once the code changed :

• do I have a way to test that my code is still working ?
• do I have a way to see if the code is actually working better than it used to be ?

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil" from Knuth, Donald. Structured Programming with go to Statements, ACM Journal Computing Surveys, Vol 6, No. 4, Dec. 1974. p.268. From wikipedia

Anyway, a few details :

• First detail I noticed : it seems like the first element of isPrime is never used (it's initialised but never read).
• Also, I am not really sure about the actual implementation of arrays of booleans but it might be interesting to have a look at bitfields to do what you are trying to do (depending on what you want to optimize).
• I have updated the question. Yes, i think i am trying to optimize the memory space here. I have left first element unused to save additional computations to arrive at the correct index. – Sumit Jain Dec 31 '11 at 15:15
• At first glance, the code seems better now :-) – SylvainD Dec 31 '11 at 15:18
• Actually, the loop "for (int i = 3; i < n; ++i) {" is still weird. Don't you want to do "i+=2" instead of "i++" ? – SylvainD Dec 31 '11 at 15:21
• oops again! i wrote correct but typed wrong – Sumit Jain Dec 31 '11 at 15:24
• The question is obviously about algorithmic optimizations and finding primes can never be too fast, so that questioning the question seems a bit out of place. – UncleBens Jan 1 '12 at 13:05

You can optimize the initialization of the array:

bool * isPrime = new bool [n/2];  // Array of random states

// But

bool * isPrime = new bool [n/2]();  // Array of zero-initialized members
// For bool this means initialization to false


If you inverse your logic (ie treat false as true and true as false)

// These two lines can be removed.
for (int i=0; i < n/2; ++i)
isPrime [i] = true;

• yes, very nice hack – Sumit Jain Dec 31 '11 at 19:02

The algorithm hinges on tracking the effect of each "prime less than i" on each "odd value less than n" as i ranges to n.

The current implementation tracks this effect per "odd value less than n", suggesting a required peak memory footprint of n/2 bits.

An alternative whose memory use scales better is to track the effect per "prime less than i" (as i ranges up to n), which requires more storage (like sizeof(n)) per entry but for fewer entries by far, especially for larger values of n. In other words, there's less to remember when you determine the effect of prior primes (all at once) on each odd number (taken one at a time).

Edited to add requested detail:

To 100% sacrifice cpu for memory, preallocate or "grow" an int vector for primes (p) from 3 to sqrt(n).

    for each i from 3 to n,
for each p so far,
if (i % p == 0) break;
if (i % p == 0) continue;
print i
if i <= sqrt(n) add i as next p

// The vector of all PRIMEs <= sqrt(n) can be small, for respectable-sized n.
// That's < 60 elements (bytes or shorts) for n < 2^16,
// and < 7000 elements (shorts or ints) for n < 2^32,

// That beats n/16 bytes.

// SO for speed, use a vector of p,m (prime,multiple) int pairs:

for each i from 3 to n,
for each p,m entry so far,
if (i>m) m=((i/p)+1)*p; // m is lowest multiple of p >= i
if (i==m) break;
if (i==m) continue;
print i
if i <= sqrt(n) add i,3*i as next p,m

• can you explain it in detail..i understand that you want to store result in an integer instead of bool – Sumit Jain Dec 31 '11 at 19:01

Initialize the boolean array to true, then from 2 to the square root of the upper bound, if the number is prime, eliminate all multiples of that number.

So, start with 2... so 2*i should all be set to false.

Then if 3 isPrime , do 3*i and set all of those to false.

Continue up the the sqrt of the upper bound.

• This answer implies that the OP's code does not do these things, but the OP's code does do them.... and does them better than what's suggested here. – rolfl Dec 21 '16 at 4:19