Prime Number Generator in C++
This quick programming tutorial guides generating all the prime numbers within a given range using the simple, intuitive method and an efficient square-root method.
Prime Numbers
A prime number is a number divisible by one or by itself only; for example, 17 is a number only divisible by either one or itself. The only possible factor for a prime number P is P * 1.
Let’s have a look at the set of prime numbers:
Set of Prime Numbers = {2, 3, 5 , 7, 11, 13, 17, 23, .....,89, 97, .... }
In C++, we can code such scenarios and generate the prime numbers within some range and even check whether a number is a prime number or not.
Generate Prime Numbers in C++
The logic behind checking whether a number is prime is to check its modulus with all numbers up to half of that number. If its modulus with any of the numbers is 0, then the number is not prime; otherwise, it is prime.
Let’s look into the simplest and most intuitive method:
#include <iostream>
using namespace std;
int main() {
int start = 0, end = 100, n;
bool ifPrime = true;
cout << "Prime numbers in between " << start << " and " << end
<< " are the following: " << endl;
while (start < end) {
ifPrime = true;
if (start == 0 || start == 1) {
ifPrime = false;
}
for (n = 2; n <= start / 2; ++n) {
if (start % n == 0) {
ifPrime = false;
break;
}
}
if (ifPrime) cout << start << ", ";
++start;
}
return 0;
}
We have taken two variables in the above code segment, start and end. The start variable is initialized to zero, and the end variable is initialized to 100 because we need prime numbers from 0 to 100.
This range can be changed anytime or can be taken as input from the user as well.
We created a loop from start to end; in that loop, we made another for loop to check if the start number is divisible by the numbers up to half of this number. It is because, for a non-prime number N, there can only be factors with numbers a and b such that a*b where a<N/2 and b<N/2.
Therefore, if the inner for loop lets the n approach half of the start value, the loop terminates, and the number is printed by line 25 as the ifprime is still true. However, if any value of n properly divides the start value, the condition at line 19 becomes true, setting the ifprime to false and terminating the for loop.
Output:
Use the sqrt() Method to Generate Prime Numbers in C++
The simple prime number calculation method discussed earlier was inefficient as it still requires us to divide until half of the number to check if it is prime or not. However, we can exploit Mathematical facts to reduce the complexity of our program running time.
The program takes help from the fact that for a factor a*b to be equal to a number N, either a or b must be less than or equal to the square root of N. For example, for 36, the possible factor pairs are (9*4), (18*2), (12*3), (6*6), so every pair has a or b less than the square root of 36.
Therefore, for disapproving a number N to be not a prime, we only need to check whether it is divisible by any number less than the square root of N or not. If it is not, that means the number is prime.
Now, let’s code the scenario:
#include <math.h>
#include <iostream>
using namespace std;
int main() {
int start = 0, end = 100, n;
bool ifPrime = true;
cout << "Prime numbers in between " << start << " and " << end
<< " are the following: " << endl;
while (start < end) {
ifPrime = true;
if (start == 0 || start == 1) {
ifPrime = false;
}
for (n = 2; n <= sqrt(start); ++n) {
if (start % n == 0) {
ifPrime = false;
break;
}
}
if (ifPrime) cout << start << ", ";
++start;
}
return 0;
}
We have created a loop from start to end, and in that loop, we will take a square root of the number, which will be the truncating number for the inner loop.
An inner loop will check if the current number is divisible by any number up to its square root. If not, we print it as a prime number.
Output: