Quick Prime Number Test - Method: Advanced

While the last Quick Prime Number Test was done at a basic level, today we are going to advance and used much more from what can be done in C++. The declarations will now be the following: Let us clarify what these are for! The bitwise shifting operator () is used to shift bits to the left. X N would mean that the number X, in binary representation, will be shifted left with N positions. For example, let's look at the following: This will output 128! This happens because from the right side, a 0 bit enters, and to the left, since int is 4 bytes or 32 bits on most platforms, it will simply move left and eliminate the leftmost bit. The elimination would happen in any case, regardless of the bit's value (0 or 1). So, a way to calculate 2^N is 1main.cpp source code. We have re-written the one from the last prime test tutorial, to work with the masks and the new form of representation.

1. #include <iostream>
2.  
3. #define N 1<<20
4. #define M 1<<17
5.  
6. typedef unsigned char uchar;
7.  
8. using namespace std;
9.  
10. uchar isPrime[M];
11. uchar masks[8] = {1, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7};
12.  
13. void init(int n) {
14.     int i;
15.     for (i = 0; i <= n; i++) {
16.         isPrime[i] = 255;
17.     }
18. }
19.  
20. void FindPrimesTo(int n) {
21.     int group, order;
22.     group = 0;
23.     isPrime[group] ^= 1 << 7;
24.     isPrime[group] ^= 1 << 6;
25.     int index1, index2;
26.     for (index1 = 2; index1 <= n; index1++) {
27.         group = index1 / 8;
28.         order = 7 - (index1 % 8);
29.         if ((isPrime[group]&(1 << order)) > 0) {
30.             for (index2 = index1 * 2; index2 <= n; index2 += index1) {
31.                 group = index2 / 8;
32.                 order = index2 % 8;
33.                 isPrime[group] = (isPrime[group] & masks[7 - order]) ? (isPrime[group]^masks[7 - order]) : isPrime[group];
34.             }
35.         }
36.     }
37. }
38.  
39. int main(int argc, char** argv) {
40.     init((M) - 1);
41.     FindPrimesTo((N) - 1);
42.  
43.     cout << " PRIME TEST APPLICATION" << endl;
44.     cout << " ----------------------" << endl;
45.     cout << " Enter 0 to exit!" << endl << endl;
46.     int option = 1, nr;
47.     while (option != 0) {
48.         nr = -1;
49.         while ((nr < 0) || (nr > 1000000)) {
50.             cout << " nr = ";
51.             cin >> nr;
52.         }
53.         option = nr;
54.         cout << " ";
55.         int group = nr / 8;
56.         int order = nr % 8;
57.         if (isPrime[group] & masks[7 - order]) {
58.             cout << nr << " is a prime number!";
59.         } else {
60.             cout << nr << " is not a prime number!";
61.         }
62.         cout << endl;
63.     }
64.     cout << " Done! Now exiting ..." << endl;
65.     return 0;
66. }

Now, you can tell anyone you know advanced C++ and even test primes like this! Enjoy!