Today we will learn the prime number program in C++ and how to check whether the given number is prime or not. So before learning, you should have a piece of knowledge about a prime number.so first of all,
Table of Contents
What are Prime Numbers?
Any natural number which can be divisible by itself or the number which has only two factors i.e 1 and the number itself are called prime numbers.
For example 2,3,5,7,11 and so on…
Note: The number 2 is only even prime number because most of the numbers are divisible by 2.
Prime Number Algorithm:
1st Step: START.
2nd Step: Enter the number to Check for prime.
3rd Step: if the number is divisible by any other number and also divisible by itself then print “Number is Prime Number”.
4th Step: Else print “Number is not a Prime Number”.
5th Step: STOP.
1. Prime Number Program in C++
In this program, the compiler will ask the user to enter the number which user wants to check whether the number is prime or not. And after checking the compiler will print the output on the screen.
#include <iostream>
using namespace std;
int main()
{
int n, i;
bool isPrime = true;
cout << "Enter a positive integer: ";
cin >> n;
for(i = 2; i <= n / 2; ++i)
{
if(n % i == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
cout << "This is a prime number";
else
cout << "This is not a prime number";
return 0;
}Output:
Explanation:
let us consider n=5 for loop becomes for(i=1; i<5; i++)
1st Iteration: for(i=1; i<=5; i++) in 1st iteration i is incremented i.e the value of i for the next iteration is 2.If (n%i==0) then c is incremented i.e (5%1==0) then c is incremented.Here, (5%1=0) so c is incremented i.e c=1.
2nd Iteration: for(i=2;i<=5;i++) in 2nd iteration i is incremented i.e the value of i for the next iteration is 3.If (n%i==0) then c is incremented i.e (5%2==0) then c is incremented.here,(5%2!=0) so c is not incremented i.e c=1.
3rd Iteration: for(i=3;i<=5;i++) in 3nd iteration i is incremented i.e the value of i for the next iteration is 4.If (n%i==0) then c is incremented i.e (5%3==0) then c is incremented.Here,(5%3!=0) so c is not incremented i.e c=1.
4th Iteration: for(i=4;i<=5;i++) in 4th iteration i is incremented i.e the value of i for the next iteration is 5.If (n%i==0) then c is incremented i.e (5%4==0) then c is incremented.Here,(5%4!=0) so c is not incremented i.e c=1.
5th Iteration: for(i=5;i<=5;i++) in 5th iteration i is incremented i.e the value of i for the next iteration is 6.If (n%i==0) then c is incremented i.e (5%5==1) then c is incremented.Here,(5%5=0) so c is incremented i.e c=2.
6th Iteration: for(i=6;i<=5;i++) in 6th iteration the value of i is 6 which is greater than n i.e i>n(6>5) so the for loop is terminated.Here c=2 so the given number is prime number.
Time Complexity of This solution is O(n).
2. Program for Prime Number in C++ Using While Loop
In this program, we will use while loop instead of for loop. But, the logic behind the program in same.
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int num, i, f;
//Reading a number from user
cout<<"Enter any number:";
cin>>num;
f = 0;
i = 2;
while(i <= num/2)
{
if(num%i == 0)
{
f=1;
break;
}
i++;
}
if(f == 0)
cout<<num<<" is a Prime Number"<<endl;
else
cout<<num<<" is Not a Prime Number"<<endl;
return 0;
}Output:
3. Optimized School Method in C++
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
int main()
{
isPrime(11) ? cout << " true\n" : cout << " false\n";
isPrime(15) ? cout << " true\n" : cout << " false\n";
return 0;
}
Output:
4. C++ Program to Print Next Prime Number
In this program when the user enters any number to check whether it is prime or not then the compiler will print the next prime number occurs after the entered number by the user.
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int i,j=2,num;
cout<<"Enter any number: ";
cin>>num;
cout<<"Next prime number: ";
for(i=num+1;i<3000;i++)
{
for(j=2;j<i;j++)
{
if(i %j==0)
{
break;
} // if
} // for
if(i==j || i==1)
{
cout<<"\t"<<i;
break;
} // if
} // outer for
}Output:
In the above program, we have entered the number as 5. And the compiler printed 7 as next prime number.
5. C++ Program to Print Prime Numbers from 1 to 100
In this program, we will print all the prime numbers between 1 and 100.
#include <iostream>
using namespace std;
int isPrimeNumber(int);
int main()
{
bool isPrime;
for(int n = 2; n < 100; n++) {
// isPrime will be true for prime numbers
isPrime = isPrimeNumber(n);
if(isPrime == true)
cout<<n<<" ";
}
return 0;
}
// Function that checks whether n is prime or not
int isPrimeNumber(int n) {
bool isPrime = true;
for(int i = 2; i <= n/2; i++) {
if (n%i == 0) {
isPrime = false;
break;
}
}
return isPrime;
}Output:
6. C++ Program to print all Prime Numbers Between 1 to n
After Executing this program the compiler will ask the user to enter the number n to print all prime numbers between 1 to n. And then the compiler will start printing all the prime numbers.
#include <iostream>
using namespace std;
int isPrimeNumber(int);
int main() {
bool isPrime;
int count;
cout<<"Enter the value of n:";
cin>>count;
for(int n = 2; n < count; n++)
{
// isPrime will be true for prime numbers
isPrime = isPrimeNumber(n);
if(isPrime == true)
cout<<n<<" ";
}
return 0;
}
// Function that checks whether n is prime or not
int isPrimeNumber(int n) {
bool isPrime = true;
for(int i = 2; i <= n/2; i++) {
if (n%i == 0)
{
isPrime = false;
break;
}
}
return isPrime;
}Output:
Also Read:
![Insertion Sort Program in C++ – [Algorithm With Explanation]](https://learnprogramo.com/wp-content/uploads/2020/04/insertion-sort-program-in-c-500x383.png)
