Last Updated on May 18, 2023 by Prepbytes
We’ll talk about the C++ issue of finding a prime integer in this post. We’ll discuss prime numbers, their significance, three different approaches to identifying them in C++, all prime numbers between two numbers, etc. So let’s start with an explanation of prime numbers.
What are Prime Numbers in C++?
Prime numbers are natural numbers that can only be divided by themselves and by one (1). One outstanding example is the number 7, which consists just of the number 7 and the number 1. However, due to the presence of factors 2 and 3 in addition to factors 1 and 6, the number 6 is not prime.
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.
Facts about Prime Number in C++
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++
The problem formulation is thus quite straightforward. We are required to assess whether or not a particular number is a prime number. When given 7, for example, we will print "YES," however when given 10, we will print "NO."
So let’s examine the procedure in further depth.
Method 1: Complete Factorization Prime Number Program in C++
So, we are aware that the only numbers that can be divided by one are the prime numbers and the number itself. We also know that each integer may be divided by one and by itself. There is no need to check that, therefore.
So, the negation approach is as follows. This implies that rather than verifying or demonstrating that the number is a prime, we will instead attempt to demonstrate that it is not a prime (composite or 1). The number will be presumed to be a prime number if we are unable to disprove its primality.
Consequently, we may use the algorithm below.
Algorithm to Check Prime Number in C++
- 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”
- 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”
- 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 prime number in c++: 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) prime number in c++: Since we have not used any extra space, the auxiliary space is O(1).
Method 2: Half Factorization Prime Number Program in C++
We may easily determine whether a given number is a prime number by iterating from 2 to N-1, as we showed. However, this strategy is not very optimized if we are given a huge number as input.
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 prime number in C++: 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) prime number in c++: 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++
As we observed with the prior approach, we were able to cut the number of iterations in half. The temporal complexity is unchanged, though. Mathematical reasoning was used to justify cutting the iterations in half.
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 of prime number in C++: 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) of prime number in C++: 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 13Conclusion
In conclusion, we have discussed the implementation of a Prime Number Program in C++. We started by understanding what prime numbers are and their properties. Then, we went through the step-by-step process of developing a C++ program to check whether a given number is prime or not.
The program involves iterating through numbers from 2 to the square root of the input number and checking for divisibility. If the number is divisible by any of the previous numbers, it is not prime. Otherwise, it is considered prime.
By using this program, we can easily determine whether a given number is prime or not, providing a valuable tool for various mathematical and computational applications.
FAQs related to the Prime Number Program in C++
Q1: What is a prime number?
Ans. A prime number is a natural number greater than 1 that is divisible by only 1 and itself. In other words, a prime number has no divisors other than 1 and itself.
Q2: Why is the iteration range up to the square root of the number?
Ans. The iteration range is up to the square root of the number because any factor of the number greater than its square root would have a corresponding factor smaller than the square root. Therefore, checking for divisibility up to the square root is sufficient.
Q3: What is the time complexity of the prime number program?
Ans. The time complexity of the prime number program is O(sqrt(n)), where n is the input number. This is because we iterate up to the square root of the number to check for divisibility.
Q4: Can prime numbers be negative?
Ans. No, prime numbers are defined as natural numbers greater than 1. Negative numbers and 0 are not considered prime.
Q5: Can the program handle large prime numbers?
Ans. Yes, the program can handle large prime numbers. However, the execution time may increase significantly as the number becomes larger. For very large prime numbers, more efficient algorithms and data structures might be needed.
Q6: Can the program identify all prime numbers within a given range?
Ans. No, the program we discussed determines whether a specific number is prime or not. To find all prime numbers within a given range, you would need to modify the program to iterate through each number in the range and check its primality individually.
Q7: Are there any optimized algorithms for finding prime numbers?
Ans. Yes, there are more advanced algorithms, such as the Sieve of Eratosthenes or the Miller-Rabin primality test, that are more efficient for finding prime numbers, especially in large ranges or when dealing with a large number of primes. These algorithms are beyond the scope of our basic prime number program in C++ but can be explored for more advanced applications.
Other C++ Programs
C++ Program to Add Two Numbers
C++ Program to Reverse a Number
C++ program for heap sort
Bubble Sort in C++ with Program Code and Example
Hello world program in C++