Quick Prime Number Test - Method: Advanced

Submitted by DoctorSpeedCode on Saturday, August 9, 2014 - 18:12.
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: 
  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};
Let us clarify what these are for! The bitwise shifting operator (main.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!

Tags

Add new comment

About text formats
  • 10 views