With prime numbers, we always get a headache. We will see 2 tutorials about quick prime number testing, this one at a basic level, the next one at an advanced level.
The idea of our test is the following: We create an array of bool values, to represent numbers like this:
0 - FALSE
1 - FALSE
2 - TRUE
3 - TRUE
4 - FALSE
5 - TRUE
6 - FALSE
7 - TRUE
8 - FALSE
9 - FALSE
10 - FALSE
11 - TRUE
And so forth! Where we have TRUE, it is a prime number, where we have FALSE, it is not a prime number. How to generate such an array?
First of all, for N numbers we need N+1 elements, because array indexing in C++ goes from 0 to nr_of_elements-1. Then, we initialize 0, 1 and 2 manually. Obviously, for the beginning, we fill the array assuming every number is a prime number.
The following declarations are required:
#include <iostream>
#define N 1000001
using namespace std;
bool isPrime[N];
This is our bool array. Now let us see, how to fill the array with the right values. The initialization is simple, as all elements will be set to TRUE. Generating the prime number TRUE/FALSE values goes like this:
void FindPrimesTo(int n) {
isPrime[0] = isPrime[1] = false;
isPrime[2] = true;
int index1, index2;
for (index1 = 2; index1 <= n; index1++) {
if (isPrime[index1] == true) {
for (index2 = index1 * 2; index2 <= n; index2 += index1) {
isPrime[index2] = false;
}
}
}
}
The principle is simple, and uses the following steps:
1) 0, 1 are not primes, 2 is a prime
2) For each prime number up to n (we tested the value to be TRUE), we do the following: the prime number's multiples are not primes, so we set those to FALSE.
As you can foresee, the result will be the array with TRUE for primes, FALSE for non-primes.
For your amazement, we have created a test application, which reads numbers for prime testing, until 0 is entered. We simply ignore negative numbers in this test!
The full source code for
main.cpp is here:
#include <iostream>
#define N 1000001
using namespace std;
bool isPrime[N];
void init(int n) {
int i;
for (i = 0; i <= n; i++) {
isPrime[i] = true;
}
}
void FindPrimesTo(int n) {
isPrime[0] = isPrime[1] = false;
isPrime[2] = true;
int index1, index2;
for (index1 = 2; index1 <= n; index1++) {
if (isPrime[index1] == true) {
for (index2 = index1 * 2; index2 <= n; index2 += index1) {
isPrime[index2] = false;
}
}
}
}
int main(int argc, char** argv) {
init(N - 1);
FindPrimesTo(N - 1);
cout << " PRIME TEST APPLICATION" << endl;
cout << " ----------------------" << endl;
cout << " Enter 0 to exit!" << endl << endl;
int option = 1, nr;
while (option != 0) {
nr = -1;
while ((nr < 0) || (nr > 1000000)) {
cout << " nr = ";
cin >> nr;
}
option = nr;
cout << " ";
if (isPrime[nr] == true) {
cout << nr << " is a prime number!";
} else {
cout << nr << " is not a prime number!";
}
cout << endl;
}
cout << " Done! Now exiting ..." << endl;
return 0;
}
One of the outputs during our tests was this (and it is accurate - you can verify):
PRIME TEST APPLICATION
----------------------
Enter 0 to exit!
nr = 15
15 is not a prime number!
nr = 7
7 is a prime number!
nr = 100103
100103 is a prime number!
nr = 1000000
1000000 is not a prime number!
nr = -25
nr = 66
66 is not a prime number!
nr = 67
67 is a prime number!
nr = 0
0 is not a prime number!
Done! Now exiting ...
Enjoy and test any number of primes you wish!
