Answers to: Usefulness of Bitwise sievehttps://discuss.codechef.com/questions/106086/usefulness-of-bitwise-sieve<p>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? </p>enFri, 21 Jul 2017 15:30:28 +0530Answer by c_utkarshhttps://discuss.codechef.com/questions/106086/usefulness-of-bitwise-sieve/106102<p>Not much.</p>
<p>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)$.</p>
<p>Almost all of the online judges provide enough memory to make a boolean array of size upto $10^8$ i.e. ~<strong>100 MB</strong>. So, most of the problems can be solved using the normal Sieve. (including <a href="http://www.spoj.com/problems/TDPRIMES/">TDPRIMES</a>). Bitwise Sieve is only required when the memory limit (<strong>ML</strong>) is kept deliberately low so that the naive solutions don't pass. </p>
<p>For example: <a href="https://open.kattis.com/problems/primesieve">https://open.kattis.com/problems/primesieve</a>. Notice that the <strong>ML</strong> is only <strong>64 MB</strong>.</p>
<p>So, in general, Bitwise Seive is not of much importance in contests.</p>c_utkarshFri, 21 Jul 2017 15:30:28 +0530https://discuss.codechef.com/questions/106086/usefulness-of-bitwise-sieve/106102