You are not logged in. Please login at www.codechef.com to post your questions!

×

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?

asked 21 Jul '17, 09:47

sudip_95's gravatar image

4★sudip_95
7556
accept rate: 10%


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.

link

answered 21 Jul '17, 15:30

c_utkarsh's gravatar image

5★c_utkarsh
1.1k5
accept rate: 17%

edited 21 Jul '17, 15:33

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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: 797 times

last updated: 21 Jul '17, 15:33