How can I find prime numbers through bit operations in C++?

Question

How can I find prime numbers through bit operations in C++?

Answer 1

I think the way to do this is to not think of the bitset as its numerical representation as we normally do, but to think of it at a list of numbers. So the bitset

1111

would represent the numbers 1, 2, 3, and 4. Now if we say that a '1' represents prime and a '0' represents not prime, we can make a sieve as follows.

Set all the bits to 1 (I'm going to use 16 bits that represent the integers 1 through 16)

1111 1111 1111 1111

I know that one is not prime, so I'm setting it to zero.

0111 1111 1111 1111

Now, I know that the next '1' I encounter represents a prime, but all multiples of that number are by definition not prime, so I leave the next '1' alone, but set all of its multiples to '0'. Since the next '1' represents the number 2, I zero every second bit.

0110 1010 1010 1010

The benefit of this method over others is that as I traverse the rest of the bits, I don't need to check each one to see if it's divisible by 2 (so nothing like if i % 2 == 0 is necessary). I can just keep incrementing the index by 2 and I know I'll always land on a non-prime.

Now I just do the same thing again with the next '1' I encounter (the next prime starting from the last prime I identified, 2). I know it's prime, since it isn't divisible by any of the numbers below it. I know all of its multiples are prime, so since it's in the third position, I set every third following bit to '0'. Some of them are already '0' since they're also multiples of 2. That's okay, just leave them '0'.

0110 1010 0010 1000

The next '1' that you encounter is the fifth bit. Now you could keep going until you reach the end, but since 5 is greater than the square root of the number of bits that I started with, I know I'm not going to find any more composites, so I'm done.

---

After a little more searching I found a really good implementation example in Deitel & Deitel's C++ How to Program. They also provide good explanations of the algorithm and code.

Answer 2

Try implementing a prime sieve using a bitset. The algorithm only needs to store whether a certain number is a prime or not. One bit is sufficient for that.