C++

Forum

 
Prime numbers

Geckoo (362)
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 :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
 
#include <iostream>
#include <vector>
#include <algorithm> // to sort vector
#include <windows.h> // 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<pair<int, int>> 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
lastchance (6980)
seeplus (6457)
1
2
3
4
5
6
7
8
 
 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#include <iostream>
#include <cmath>
#include <algorithm>

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<int>(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
Geckoo (362)
Thanks seeplus. I have to use an unsigned long long int :
Max -> 18446744073709551615

And thanks lastchance for the link :)
Last edited on
lastchance (6980)
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.
seeplus (6457)
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
seeplus (6457)
RE colours. If you use windows.h, then these are pre-defined:

1
2
3
4
5
6
7
8
 
#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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#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
Geckoo (362)
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 ++

1
2
3
4
 
int inc = 1;
for (int i = min; i <= max; i += inc)
// ...
if (inc == 1 && i != 2) inc++;
Last edited on
seeplus (6457)
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.