# Prime Number Program in C++ In this article, we will discuss the problem of identifying a prime number in C++. We’ll talk about what prime numbers are, what they mean, how to recognize them in C++ in three distinct ways, all prime numbers between two numbers, etc. Therefore, let’s begin with a definition of prime numbers.

## What are Prime Numbers?

Natural numbers known as prime numbers which can only be divided by one (1) and by the number itself. One prime example is 7, which has only the number 7 itself and the number 1 as components. However, 6 is not a prime number since it has additional components, 2 and 3, in addition to factors 1 and 6.

Some examples of prime numbers are 3,5,7,11,13,17,19,23, etc.

Composite numbers are those numbers that are not prime. However, 1 is neither a prime nor a composite number in mathematics.
Most compact prime number.
2 is the smallest prime number. Since 1 is neither a prime nor a composite, this is the case. The first number after 1 that can be divided only by itself is two. Hence, the smallest prime number is 2.

Now let’s examine some useful information regarding prime numbers that you might find fascinating.

• The only even prime number is two. This is due to the fact that, other than 1 and the number itself, all other even numbers will likewise be divisible by 2.
• The only consecutive prime numbers are 2 and 3. Later, such a pair is absent.
• The only prime number that ends in five is the number five. Any subsequent number that ends in 5 will not be a prime number because it will also be divisible by 5.
• Every prime number after 2 and 3 has either the form 6n+1 or 6n-1.

Now that we are sufficiently knowledgeable on prime numbers, let us now move to the prime number program in C++.

## Prime Number Program in C++

So, the problem statement is very simple. We are given a number and we have to determine whether this number is a prime number or not. For instance, if we are given 7, we will print “YES” else if we are given 10, we will print “NO”.
So, let us understand the process in detail.

### Method 1: Complete Factorization Prime Number Program in C++

So, we know that the prime numbers are the numbers that are only divisible by 1 and the number itself. Also, we know that every number is divisible by 1 and itself. So, don’t have to check that.

So, this is the negation method. This means that instead of checking or proving that the number is prime, we will; try to prove that the number is non-prime (composite or 1). If we fail to prove the number non-prime, it will automatically be a prime number.
So, we can follow the following algorithm

### Algorithm to Check Prime Number in C++

1. Check if the input number (N) is 1. If it is 1, it is neither prime nor composite. Still, it is not prime so we will print “NO”
2. Else, iterate from 2 to N-1 and check if any number is able to divide the number N completely i.e. if any number from 2 to N-1 is a factor of N. If we find even one number that is a factor of N, N will not be a prime number as we would have a number apart from 1 and N that divides N completely. So, in this case, also, print “NO”
3. Finally, if we have iterated from 2 to N-1 and have not found any factor of N, this means that N is only divisible by 1 and N itself. So, it is a prime number. Hence, print “YES”

Now that we have understood this procedure, let us write the code for the same.

### Program for Complete Prime Factorization for finding Prime Number in C++

```#include <iostream>
using namespace std;
int main()
{
int n, i, m=0, flag=0;
cout << "Enter the Number to check Prime: ";
cin >> n;
if(n == 1) {
flag = 1;
cout<<"No"<<endl;
}
for(i = 2; i < n; i++)
{
if(n % i == 0)
{
cout<<"NO"<<endl;
flag=1;
break;
}
}
if (flag==0)
cout << "YES"<<endl;
return 0;
}
```

Time Complexity: The time complexity of this method is O(N) as we are traversing almost N numbers in case the number is prime.

Space Complexity (Auxiliary Space): Since we have not used any extra space, the auxiliary space is O(1).

### Method 2: Half Factorization Prime Number Program in C++

So, we saw that we can simply iterate from 2 to N-1 to identify whether the number given to us is prime or not. However, if there is a large number given to us as input, this method is not that optimized.

If we think carefully, we can understand that we don’t need to check till N-1. Obviously, N-1 can never divide N. So, what should be the endpoint?

Well, if a number is even, it gets divided by 2. So, its half will also be its factor. Also, if a number is odd, we can’t say that its half will be its factor. However, there will be at least 1 factor before its half also.

So, we can say that we can check if a number is prime or not by iterating from 2 to N/2. If there exists a factor between 2 to N/2, the number will be non-prime, else it will be prime.

So, let us now write the code for this method.

Code for Half Factorization to identify a Prime Number in C++

```#include <iostream>
using namespace std;
int main()
{
int n, i, m=0, flag=0;
cout << "Enter the Number to check Prime: ";
cin >> n;
if(n == 1) {
flag = 1;
cout<<"No"<<endl;
}
for(i = 2; i <= n/2; i++)
{
if(n % i == 0)
{
cout<<"NO"<<endl;
flag=1;
break;
}
}
if (flag==0)
cout << "YES"<<endl;
return 0;
}
```

Time Complexity: Well, the time complexity remains the same i.e. O(N). However, we are iterating approximately just half as compared to before since we are going till N/2.

Space Complexity (Auxiliary Space): Since we have not used any extra space, the auxiliary space is O(1).

So, we have reduced the number of iterations to half in the above method. However, can we write a prime number program in C++ with not just reduced iterations, but also reduced asymptotic time complexity. So, let us see that method.

### Method 3: Square Root Method Prime Number Program in C++

We saw in the previous method, we were able to reduce the iterations to half. Still, the time complexity remains the same. The logic for reducing the iterations to half was mathematical.

Similarly, we also have another mathematical logic that will reduce the iterations and time complexity further. Let us use 2 composite numbers. One of them should be a perfect square and the other should not be a perfect square. So, let’s say we have the two numbers 40 (not a perfect square) and 36 (perfect square). The factors of these numbers are shown below. So, can you find anything specific in these 2 factorizations? The image above shows that the upper half and lower half of factorizations are mirror images of each other.

In the case of perfect squares, the square root factor is in the middle and is not mirrored. However, the rest of the factors are mirrored.

What does this mean? This means that if the number is a composite number, whether it is a perfect square or not, there will be at least 1 factor on or before the square root of the number. This is because the factors below the square root are just mirrored images of the factors above the square root.

So, in order to check whether a number is a prime number or not, we check the factors of the number on or below the square root of the number. If there exists some factor, the number is non-prime, else it will be prime.

Now that we have understood the procedure, let us write the code for the same.

### Program for Square Root Method to identify a Prime Number in C++

```#include <iostream>
using namespace std;
int main()
{
int n, i, m=0, flag=0;
cout << "Enter the Number to check Prime: ";
cin >> n;
if(n == 1) {
flag = 1;
cout<<"No"<<endl;
}
for(i = 2; i*i <= n; i++)
{
if(n % i == 0)
{
cout<<"NO"<<endl;
flag=1;
break;
}
}
if (flag==0)
cout << "YES"<<endl;
return 0;
}
```

Time Complexity: The time complexity of this solution is root N i.e. O(√N). This is because we are traversing just √N numbers.

Space Complexity (Auxiliary Space): Since we have not used any extra space, the auxiliary space is O(1).

So, these are the three methods to identify whether a number is a prime number or not.

What would you do if we ask you to print the prime numbers in a range i.e. we give you 2 numbers, low and high and you have to print all the prime numbers between low and high. So, we can use the same method to identify a prime number as shown below and just apply a loop from low to high and if a prime number is detected, we print it. The code for the same is shown below.

### Program to print Prime Numbers in a Range

```#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
if(n == 1) return false;

for(int i=2;i*i<=n;i++) {
if(n % i == 0) return false;
}

return true;
}
int main()
{
int n, i, m=0, flag=0;
int low, high;
cin>>low;
cin>>high;
for(i = low; i <= high; i++)
{
if(isPrime(i)){
cout<<i<<" ";
}
}
return 0;
}
```
``````Output
2 3 5 7 11 13``````

So, we hope that you liked the discussion and have understood the concepts in detail. We hope you understood all the 3 methods to identify a prime number. Keep learning and moving forward. Hope to see you again at PrepBytes.

Other C++ Programs