Usefulness of Bitwise sieve

I’ve recently learned about Bitwise sieve. The only usefulness I can think of it is it can generate more primes than normal Sieve of Eratosthenes as it takes less memory. But I’ve never confronted a situation (only here - SPOJ TDPRIMES) where you can’t solve it with the normal sieve, but solve it with bitwise sieve. My question is, how much it is useful for contests?

Not much.

Since in Bitwise Sieve we use the individual bits to store whether the n^{th} number is prime or not, only the memory requirement is reduced to {1/8}^{th} versus the normal Sieve of Eratosthenes, where we use a boolean array to do the same. This however, does not improve the time complexity, its still O(N\ log\ log\ N).

Almost all of the online judges provide enough memory to make a boolean array of size upto 10^8 i.e. ~100 MB. So, most of the problems can be solved using the normal Sieve. (including TDPRIMES). Bitwise Sieve is only required when the memory limit (ML) is kept deliberately low so that the naive solutions don’t pass.

For example: https://open.kattis.com/problems/primesieve. Notice that the ML is only 64 MB.

So, in general, Bitwise Seive is not of much importance in contests.

2 Likes