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 do you find anything incorrect? Let us know in the comments. Thank you!