How can I find primes through bit operations in C ++?

Question

How can I find primes through bit operations in C ++?

Answer 1

Try a basic sieve using bit set. The algorithm should only store whether a certain number is prime or not. One bit is enough for this.

Answer 2

I think the way to do this is not to think of beetle as its numerical representation, as we usually do, but to think of it in a list of numbers. Therefore, the bit rate

1111 

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

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

 1111 1111 1111 1111 

I know that one is not simple, so I set it to zero.

 0111 1111 1111 1111 

Now I know that the next meeting "1" I represent a prime number, but all the multiples of this number are not primary by definition, so I leave only one "1", but all its multiple values ​​are equal to "0". Since the next " 1 "represents the number 2, I zero every second bit.

 0110 1010 1010 1010 

The advantage of this method over the others is that when I cross the remaining bits, I do not need to check each of them to see if it is divisible by 2 (therefore, nothing like this if i % 2 == 0 is required). I can just increase the index by 2, and I know that I will always land on non-simple.

Now I'm just doing the same thing again with the next “1” that I come across (the next prime, starting with the last first number that I identified, 2). I know this is simple, since it is not divisible by any of the numbers below. I know that all its multiples are prime, therefore, since it is in the third position, I set every third next bit to '0'. Some of them are already “0”, since they are also multiples of 2. This is good, just leave them “0”.

 0110 1010 0010 1000 

The next "1" that you come across is the fifth bit. Now you can keep going until you get to the end, but since 5 is more than the square root of the number of bits from which I started, I know that I will no longer collect composites, so I finished.

---

After a short search, I found a really good example of implementation in Deitel and Deitel C ++ How to Program . They also give good explanations of the algorithm and code.

Answer 3

I found this C # code, I'm sure you can read it well.

 using System; using System.Collections.Generic; using System.Text; namespace eratosthenes { class Program { static void Main(string[] args) { int n = 100; bool[] primes = new bool[n]; for (int i = 2; i < n; i++) { primes[i]=true; } for (int i = 2; i < n; i++) { if (primes[i] == true) { for (int j = i * i; j < n; j=j+i) { primes[j] = false; } Console.WriteLine(i); } } Console.ReadLine(); } } } 

Link to the German wikibooks page .

Answer 4

If you don’t know, then getting an answer from someone else is a hoax, no? Tell the guy you don't know. It is normal not to know every question in the interview. It looks a lot worse if he is caught cheating or copying things than saying "I don't know." Explain how you know what a prime number is, explain some properties of primes, and explain what you know about bit operations. If you do not know this, perhaps this work is not for you?