### Prime numbers

Hello everyone. I hope that all is fine for you.
Today I worked on a little code so as to compute prime numbers - a simple demonstration giving a vision about a fact : there is no pattern or scheme in order to determine the gap between some prime numbers. Of course, I know that some spirals give us a regular (more or less) pattern, but nothing really predictable or precise. Prime numbers are captivating...
I would like to show you this code. Maybe you could improve some parts. You are skilled and full of plenty of useful advice. Let me know what you think about it.

The code has different parts :
check the higher gap,
check how many prime numbers are found between two integers,
check how many occurrences there is for each gap...

Also I added a bytes representation of the prime numbers. Stupidly I said to myself that perhaps there is a pattern or something readable. Of course, there is nothing. Finally I wrote this code as a demonstration that there is ... no demonstration :)

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169`` ``````#include #include #include // to sort vector #include // console handle // as usual using namespace std; #define color_black 0 #define color_dark_blue 1 #define color_dark_green 2 #define color_light_blue 3 #define color_dark_red 4 #define color_magenta 5 #define color_orange 6 #define color_light_gray 7 #define color_gray 8 #define color_blue 9 #define color_green 10 #define color_cyan 11 #define color_red 12 #define color_pink 13 #define color_yellow 14 #define color_white 15 // functions' declaration void intro(); void dataProcessing(int o); void decToBinary(int n); HANDLE hConsole; vector> vgap; // pair for gap and its occurrence int main() { hConsole = GetStdHandle(STD_OUTPUT_HANDLE); int min, max, prime, o; int previous = 0; int gap = 0; // higher gap int num = 0; // how many prime numbers have been found? intro(); SetConsoleTextAttribute(hConsole, color_yellow); cout << "Enter the lower limit -> "; SetConsoleTextAttribute(hConsole, color_orange); cin >> min; SetConsoleTextAttribute(hConsole, color_yellow); cout << "Enter the upper limit -> "; SetConsoleTextAttribute(hConsole, color_orange); cin >> max; SetConsoleTextAttribute(hConsole, color_yellow); cout << "Prime numbers list : " << endl << endl; // check some bad entries if (min >= max || min <= 1) { SetConsoleTextAttribute(hConsole, color_dark_red + (color_light_gray * 16)); cout << "*** Something goes wrong here! ***" << endl << endl; SetConsoleTextAttribute(hConsole, color_white); return 0; } for (int i = min; i <= max; i++) { prime = 1; for (int j = 2; j < i; j++) if (i % j == 0) { prime = 0; break; } if (prime == 1) { if (previous == 0) previous = i; num++; SetConsoleTextAttribute(hConsole, color_cyan); cout << i << "\t"; decToBinary(i); o = (i - previous); SetConsoleTextAttribute(hConsole, color_magenta); if ((o != 0) ? cout << "\t" << o << endl : cout << "\t" << "*" << endl); if (o > gap) gap = o; // new higher gap dataProcessing(o); previous = i; } } // sort vector pair sort(vgap.begin(), vgap.end()); // display results SetConsoleTextAttribute(hConsole, color_yellow); cout << "\n" << "--------------------------------------------" << endl; cout << "Between numbers " << min << " and " << max << ", we got "; SetConsoleTextAttribute(hConsole, color_orange); cout << num; SetConsoleTextAttribute(hConsole, color_yellow); cout << " prime numbers (maximum gap : "; SetConsoleTextAttribute(hConsole, color_orange); cout << gap; SetConsoleTextAttribute(hConsole, color_yellow); cout << ") " << endl << endl; for (int i = 1; i < vgap.size(); ++i) { SetConsoleTextAttribute(hConsole, color_cyan); cout << "gap " << vgap[i].first; SetConsoleTextAttribute(hConsole, color_orange); cout << "\t\t" << vgap[i].second; SetConsoleTextAttribute(hConsole, color_cyan); cout << " occurrence(s)" << endl; } SetConsoleTextAttribute(hConsole, color_white); return 0; } // simple intro function with info void intro() { SetConsoleTextAttribute(hConsole, color_dark_red + (color_light_gray * 16)); cout << "**********************************" << endl; cout << "*** Playing with prime numbers ***" << endl; cout << "**********************************" << endl; cout << endl; SetConsoleTextAttribute(hConsole, color_white); } // data processing in vector pair void dataProcessing(int o) { for (int i = 0; i < vgap.size(); i++) if (vgap[i].first == o) { // so it exists - increment second ++ vgap[i].second++; return; } // this point is only reached if the gap does not exist vgap.push_back(make_pair(o, 1)); // create a new pair } // function to convert decimal to binary void decToBinary(int n) { int binaryNum[1000] = {}; int bits = 8; int i = 0; while (n > 0) { binaryNum[i] = n % 2; n = n / 2; i++; } if (i > 8) bits = 8 * ((i + 7) / 8); for (int j = bits - 1; j >= 0; j--) { if ((binaryNum[j] == 1) ? SetConsoleTextAttribute(hConsole, color_green) : SetConsoleTextAttribute(hConsole, color_dark_red)); cout << binaryNum[j]; } }``````

 ``` ********************************** *** Playing with prime numbers *** ********************************** Enter the lower limit -> 77 Enter the upper limit -> 123 Prime numbers list : 79 01001111 * 83 01010011 4 89 01011001 6 97 01100001 8 101 01100101 4 103 01100111 2 107 01101011 4 109 01101101 2 113 01110001 4 -------------------------------------------- Between numbers 77 and 123, we got 9 prime numbers (maximum gap : 8) gap 2 2 occurrence(s) gap 4 4 occurrence(s) gap 6 1 occurrence(s) gap 8 1 occurrence(s) ```
Last edited on
 ``12345678`` `````` prime = 1; for (int j = 2; j < i; j++) if (i % j == 0) { prime = 0; break; }``````

This loop to determine if prime or not can be made more efficient (without using another algorithm such as a sieve). Primes are always odd (except for 2 - treat as a special case) and for testing by remainder, the divisor to be tested can stop at <= sqrt(number). Also, apart from 2 & 3 there are no consecutive prime numbers. Perhaps:

 ``1234567891011121314151617181920212223242526`` ``````#include #include #include void primes(int num1, int num2) { if (num1 == 2) std::cout << num1 << ' '; int ctr { (num1 = num1 < 1 ? 1 : num1) < 3 }; for (int i = std::max(3, num1 + !(num1 % 2)), got; got = true, i <= num2; ctr += got, i += 2) { for (int j = 3, k = static_cast(sqrt(i)); got && j <= k; got = (i % j) != 0, j += 2); if (got) std::cout << i << ' '; } std::cout << "\nThere are " << ctr << " primes\n"; } int main() { const int min { 77 }, max { 123 }; primes(min, max); }``````

 ``` 79 83 89 97 101 103 107 109 113 There are 9 primes ```

Also if you want to look at large number primes, you'll need to change type from int to maybe unsigned long long int (64 bit). If you do investigate large primes, you'll then definitely want to investigate more efficient methods of obtaining prime numbers.
Last edited on
Thanks seeplus. I have to use an unsigned long long int :
Max -> 18446744073709551615

And thanks lastchance for the link :)
Last edited on
Take a squint at
https://en.wikipedia.org/wiki/Prime_number_theorem

In terms of patterns, there are estimates of the total number of primes up to N (in an asymptotic limiting case) and the average gap between primes.

But if you find a "pattern" in the primes - other than asymptotic limiting properties - then you will make a fortune.
Another book which could be of interest:

Dr. Riemann's Zeros
https://smile.amazon.co.uk/Dr-Riemanns-Zeros-Karl-Sabbagh/dp/1843541009/ref=sr_1_5
RE colours. If you use windows.h, then these are pre-defined:

 ``12345678`` ``````#define FOREGROUND_BLUE 0x0001 // text color contains blue. #define FOREGROUND_GREEN 0x0002 // text color contains green. #define FOREGROUND_RED 0x0004 // text color contains red. #define FOREGROUND_INTENSITY 0x0008 // text color is intensified. #define BACKGROUND_BLUE 0x0010 // background color contains blue. #define BACKGROUND_GREEN 0x0020 // background color contains green. #define BACKGROUND_RED 0x0040 // background color contains red. #define BACKGROUND_INTENSITY 0x0080 // background color is intensified. ``````

Based upon these, then you can define other colours in terms of these. Perhaps:

 ``123456789101112131415161718192021222324252627`` ``````#define FOREGROUND_WHITE (FOREGROUND_RED | FOREGROUND_BLUE | FOREGROUND_GREEN) #define FOREGROUND_YELLOW (FOREGROUND_RED | FOREGROUND_GREEN) #define FOREGROUND_CYAN (FOREGROUND_BLUE | FOREGROUND_GREEN) #define FOREGROUND_MAGENTA (FOREGROUND_RED | FOREGROUND_BLUE) #define FOREGROUND_BLACK 0 #define FOREGROUND_INTENSE_RED (FOREGROUND_RED | FOREGROUND_INTENSITY) #define FOREGROUND_INTENSE_GREEN (FOREGROUND_GREEN | FOREGROUND_INTENSITY) #define FOREGROUND_INTENSE_BLUE (FOREGROUND_BLUE | FOREGROUND_INTENSITY) #define FOREGROUND_INTENSE_WHITE (FOREGROUND_WHITE | FOREGROUND_INTENSITY) #define FOREGROUND_INTENSE_YELLOW (FOREGROUND_YELLOW | FOREGROUND_INTENSITY) #define FOREGROUND_INTENSE_CYAN (FOREGROUND_CYAN | FOREGROUND_INTENSITY) #define FOREGROUND_INTENSE_MAGENTA (FOREGROUND_MAGENTA | FOREGROUND_INTENSITY) #define BACKGROUND_WHITE (BACKGROUND_RED | BACKGROUND_BLUE | BACKGROUND_GREEN) #define BACKGROUND_YELLOW (BACKGROUND_RED | BACKGROUND_GREEN) #define BACKGROUND_CYAN (BACKGROUND_BLUE | BACKGROUND_GREEN) #define BACKGROUND_MAGENTA (BACKGROUND_RED | BACKGROUND_BLUE) #define BACKGROUND_BLACK 0 #define BACKGROUND_INTENSE_RED (BACKGROUND_RED | BACKGROUND_INTENSITY) #define BACKGROUND_INTENSE_GREEN (BACKGROUND_GREEN | BACKGROUND_INTENSITY) #define BACKGROUND_INTENSE_BLUE (BACKGROUND_BLUE | BACKGROUND_INTENSITY) #define BACKGROUND_INTENSE_WHITE (BACKGROUND_WHITE | BACKGROUND_INTENSITY) #define BACKGROUND_INTENSE_YELLOW (BACKGROUND_YELLOW | BACKGROUND_INTENSITY) #define BACKGROUND_INTENSE_CYAN (BACKGROUND_CYAN | BACKGROUND_INTENSITY) #define BACKGROUND_INTENSE_MAGENTA (BACKGROUND_MAGENTA | BACKGROUND_INTENSITY) ``````

Last edited on
Thank you seeplus for the relevant comment above - about the incrementation. Your code is clever. I put a single modification in mine which increments the integer when the process finds the first prime number (except 2). After this operation, the increment integer is 2 - and all checked numbers will be odd ++

 ``1234`` ``````int inc = 1; for (int i = min; i <= max; i += inc) // ... if (inc == 1 && i != 2) inc++;``````
Last edited on
Yes - but as I said above, this is an in-efficient algorithm. For dealing with large numbers there are more efficient ones.

Note that it is more efficient to do an unwanted addition than to have an if statement which can cause branching in the cache

 `` `` ``inc += inc == 1 && i != 2;``

This will either increment inc by 1 or 0.

but then (not tried):

 `` `` ``for (int = min, inc = 1; i <= max; inc += inc == 1 && i != 2, i += inc)``

Last edited on
Topic archived. No new replies allowed.