×

# Usefulness of Bitwise sieve

 0 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? asked 21 Jul '17, 09:47 4★sudip_95 755●6 accept rate: 10%

 0 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. answered 21 Jul '17, 15:30 1.1k●5 accept rate: 17%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×301
×184

question asked: 21 Jul '17, 09:47

question was seen: 755 times

last updated: 21 Jul '17, 15:33