C++ Program To Check Prime Number

Problem Analysis

A prime number is a natural number greater than 1 and has only two factors 1 and itself. For example 3 is a prime number, as it is a natural number and has only two factors 1 and itself (1 x 3 = 3).

If a number is prime then it is said to satisfy the property of primality. To check whether the given number is prime or not, a division method is used. In this method it is checked whether the number n is a multiple of any integer between 2 and square root n.

Integers can be expressed as (6m+n) for some integer value of m and for n = -1, 0, 1, 2, 3, 4.

2 can divide (6m+0), (6m+2), (6m+4) and 3 can divide (6m+3). Thus, every prime number which is greater than 3 can be expressed as (6m ± 1).

1 (One) should be eliminated as it is not a prime number. Multiples of 2 and 3 should be truncated to remove composite numbers below 25.

Problem Description

To develop C++ Program To Check Prime Number two program logic can be used.

In the first logic, natural number input is taken from the user and the number is divided by 2 and the quotient is stored in a variable. Then the given input is divided by numbers from 2 till quotient. If on division we get remainder 0 then it is concluded that the number is not prime.

In the second logic, 1 is eliminated and it is not checked for prime numbers. If the given integer input is 2 or 3 then without doing any computation the program concludes that the input number is prime. If the input number is 1 and on division by 2 or 3 we get remainder 0 then the program should print that the number is not prime. If both of these conditions do not work then the number is further divided by other natural numbers less than the number input by the user.

Sòlution to Problem

Following is the code to check whether the number is prime or not.

C++ Program to Check Prime or Not using divide by 2 logic

#include <iostream>  
using namespace std;  
int main( )  
{  
  int num, q, res=0, f=0;  
  cout << "Input Number to check Prime: ";  
  cin >> num;  
  res=num/2;  
  for(q = 2; q <= res; q++)  
  {  
      if(num % q == 0)  
      {  
          cout<<"Input Number not Prime."<<endl;  
          f=1;  
          break;  
      }  
  }  
  if (f==0)  
      cout << "Input Number Prime."<<endl;  
  return 0;  
}

Output:

Input Number to check Prime: 33
Input Number not Prime.

Code Analysis


In the above code integer variable num is declared. Input is taken from the user in this variable. This is done by following programming instructions:

                     cout <> num;

Given input is divided by 2 and stored in user defined variables. This is done by following programming instructions:

res=num/2; 

Within the for loop, the number is checked for its primalitty. Given input is divided by number beginning from 2 till the value stored in user defined variable res. Following is the programming instructions:

                       for(q = 2; q <= res; q++)  
                       {  
                             if(num % q == 0)  
                            {  
                                 cout<<"Input Number not Prime."<<endl;  
                                          f=1;  
                                          break;  
                            }  
                       }  
 
When this code is executed successfully then the given input is displayed on the output window with the message that it is a prime number.

C++ Program to Check Prime or Not using linked list

#include <iostream>
#include<stdio.h>

using namespace std;

struct Prime_Node
{
   int prime_data;
   Prime_Node* prime_next;  
};
void prime_push(Prime_Node** prime_head_re, int prime_nw_data)
{
    Prime_Node* prime_nw_node = new Prime_Node;
    prime_nw_node -> prime_data = prime_nw_data;
    prime_nw_node -> prime_next = (*prime_head_re);
    (*prime_head_re) = prime_nw_node;
}

int Check_Prime(int num)
{
    int q;
    if((num == 2)||(num == 3))
    {
        return num;
    }
    if(num == 1 || num%2 == 0 || num%3 == 0)
    {
        return -1;
    }
    for( q = 5; q *1 <num; q = q+6)
    {
             if(num % q == 0 || num % (q+2) == 0)
             {
                   return num;
             }
    }  
}
void ret_Prime(Prime_Node** prime_head_re)
{
     Prime_Node* ptr = *prime_head_re;
     while(ptr!=NULL)
     {
        int p = Check_Prime(ptr->prime_data);
        if(p != -1)
        {
          std::cout<< p <<" ";
        }
        ptr = ptr -> prime_next;
     }
}

int main( )
{
     Prime_Node* head = NULL;
     prime_push(&head, 8);
     prime_push(&head, 11);
     prime_push(&head, 1);
     prime_push(&head, 7);
     prime_push(&head, 54);
     prime_push(&head, 3);
     prime_push(&head, 2);
     cout<<"Prime nodes are: ";
     ret_Prime(&head);
     return 0;
}

Output:

Prime nodes are: 2 3 7 11

Code Analysis


This code contains a user defined structure having two member elements prime_data and prime_next. Prime_data is an integer type variable and prime_next is a self-referencing structure element. Following is the code to declare structure.

                               struct Prime_Node
                               {
                                      int prime_data;
                                      Prime_Node* prime_next;  
                                };

The program has three user-defined functions. These are:

void prime_push (Prime_Node** prime_head_re, int prime_nw_data)
int Check_Prime(int num)
void ret_Prime(Prime_Node** prime_head_re)

Linked list of numbers is created with the help of the function prime_push ( Prime_Node** prime_head_re, int prime_nw_data).

In function prime_push ( Prime_Node** prime_head_re, int prime_nw_data) node of linked  list is created by executing following instructions:

Prime_Node* prime_nw_node = new Prime_Node;

When a new node is created, number is input in the data part of the new node with the help of following instruction:

prime_nw_node -> prime_data = prime_nw_data;

Next part of the new node keeps the address of the next node, when the first node is created it keeps null. Following is the code to implement it:

prime_nw_node -> prime_next = (*prime_head_re); 

Address of new node is kept by *prime_head_re. This is done by executing following instruction:

(*prime_head_re) = prime_nw_node;

Function Check_Prime(int num) contains code to check the primality of a number.  It has an integer type argument named num.

Value of variable num is checked for value 2 or 3 if num is 2 or 3 then num is returned. This is done by following code: 

                      if((num == 2) || (num == 3))
                      {
                           return num;
                      }

Again the value of num is checked for value 1 or remainder is 0 on modulo division 2 or 3. If num is 1 or remainder is 0 on modulo division with 2 or 3 then value (-1) is returned. This is done by following code:

                     if( num == 1 || num%2 == 0 || num%3 == 0)
                     {
                           return -1;
                     }

Variable num is again checked for its primality within the for loop by dividing it by 5 and checking for value of remainder. If the remainder is 0 then num is returned. This has been explained in the problem analysis section.

Conclusion

This program checks whether the input number is prime or not. Two C++ programs are given to check primality. First program uses the logic similar to divide-and-conquer as it divides the number by 2 and then checks for primality.Second program checks whether the number is prime or not by using three conditions, explanation of these conditions is given in Code analysis section.

Both programs run successfully and display output as – Input number is prime Or Input number is not prime.