# Prime Number Program in C++

Prime Number Program in C++ | A natural number that has only two factors ( 1 and itself ) is called a prime number. For example, 5 is a prime number because it has only two factors 1 and 5. Similarly, 9 is not a prime number because it has more than 2 factors that are 1,3, and 9.

To develop a C++ program to check the prime number; first, you should know how to find out all factors of a number. If any number has more than 2 factors then only, it is a prime number. All negative numbers, 0 and 1 are not the prime numbers.

``````// C++ program to check prime number
// using for loop
#include<iostream>
using namespace std;
int main()
{
// declare variables
int num, count=0;

// take inputs
cout << "Enter a Positive Integer: ";
cin >> num;

// check for negative numbers and 1
if(num<=1) count++;

// check for prime
for (int i=2; i <= num/2; i++)
{
if (num % i == 0){
count++;
break;
}
}

// display result
if (count == 0)
cout << "Prime Number." << endl;
else
cout << "Not a Prime Number." << endl;

return 0;
}``````

Output for the different test-cases:-

Enter a Positive Integer: 10
Not a Prime Number.

Enter a Positive Integer: 11
Prime Number.

## Prime Number Program in CPP Using For Loop

``````// C++ program to check prime number
// using for loop
#include<iostream>
using namespace std;
int main()
{
// declare variables
int num, count=0, i=2;

// take inputs
cout << "Enter a Positive Integer: ";
cin >> num;

// check for negative numbers and 1
if(num<=1) count++;

// check for prime
while(i <= (int)num/2) {
if(num%i == 0) {
count++;
break;
}
i++;
}

// display result
if (count == 0)
cout << "Prime Number." << endl;
else
cout << "Not a Prime Number." << endl;

return 0;
}``````

## C++ Code For Prime Number with Optimization

The above programs are right and give correct output but they give less performance, their time complexity were O(n/2). We can optimize the above programs.

There are some points we should keep in mind to develop the best prime program in C++ which will give high performance.

• All negative numbers, 0 and 1 are not the prime numbers.
• 2 is the only even prime number.
• Every prime number (except 2 and 3) can be presented in the form of 6n+1 or 6n-1
• 2 and 3 are the only two consecutive natural numbers which are prime too.

In the above programs we checked number from 1 to n/2, it is better to check only from 1 to √n. Combining all these statements the C++ program for finding prime number can be written as,

``````#include<iostream>
#include<math.h>
using namespace std;
// function declaration
int isPrime(int number) ;
// main function
int main()
{
// declare variable
int n;
int prime = 1;

// take input
cout << "Enter an Integer number: ";
cin >> n;

// check prime
prime = isPrime(n);

// display result
if(prime != 0)
cout << n << " is a Prime number." << endl;
else
cout << n << " is not a Prime number." << endl;

return 0;
}

// function to check prime number
int isPrime(int number)
{

// negative numbers, 0 and 1 are
// not a prime number
if( number <= 1 ) return 0;

// 2 and 3 are prime numbers
if( number <= 3 ) return 1;

// numbers divisible by 2 and 3
// are not prime number
if(number%2==0 || number%3==0)
return 0;

// logic for remaining numbers
for(int i=5; i <= sqrt(number); i=i+6)
{
// 6k+1 => number%i
// 6k-1 => number % (i+2)
if(number%i == 0 || number%(i+2) == 0)
return 0;
}

// if all above conditions are not satisfied
return 1;
}``````

Output for the different test-cases:-

Enter an Integer number: 7
7 is a Prime number.

Enter an Integer number: 10
10 is not a Prime number.

## Check Prime Number Using Recursion

A function/method that contains a call to itself is called the recursive function/method. A technique of defining the recursive function/method is called recursion.

The recursive function/method allows us to divide the complex problem into identical single simple cases that can be handled easily. This is also a well-known computer programming technique: divide and conquer.

``````#include<iostream>
#include<math.h>
using namespace std;
// function declaration
int isPrime(int, int) ;
// main function
int main()
{
// declare variable
int n;
int prime = 1;

// take input
cout << "Enter an Integer number: ";
cin >> n;

// check prime
prime = isPrime(n, 2);

// display result
if(prime != 0)
cout << n << " is a Prime number." << endl;
else
cout << n << " is not a Prime number." << endl;

return 0;
}

// function to check prime number
int isPrime(int number, int i)
{
// negative numbers, 0 and 1 are
// not a prime number
if( number <= 2 )
return (number != 2) ? 0 : 1;

if( number % i == 0 ) return false;
if( i*i > number ) return true;

// check for the next
return isPrime(number, i+1);
}``````

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or you find anything incorrect? Let us know in the comments. Thank you!