C Program To Check whether a number is prime or not

A number is called a prime number if it is divisible only by itself and one. This means that the prime numbers have only two factors - one and the number itself.

A number is called a composite number if it has more than two factors.

A point to be noted here is that 1 is neither a prime number nor a composite number.

Conditions for a number to be prime:

It should be greater than one.
It shouldn't have more than 2 factors. It should be divisible only by 1 and the number itself.

These are some prime numbers: {2,3,5,7,11,....}.

Here, in this program, we are given a number, say n, and our task is to check whether the given number is prime or not. But before moving forward, if you are not familiar with the concept of loops in C, do check the article on Loops in C.

Input: Enter the number: 13

Output: 13 is a prime number

This problem can be solved in the following ways:

Using For Loop
Using Function
Using sqrt(n) approach
Using a recursive function

Let us look at each of these methods separately.

Method 1: C Program to Check whether a number is prime or not Using for loop

In this method, we directly check whether the number is prime or not in the main function by using a for loop.

We divide the given number, say n, by all possible divisors which are greater than 1 and less the number. It any of them divides the number, the given number is composite because it can be divided by number other than 1 and n.

Algorithm:

Declare variables n and count. Initialize count with 0. We will store the number of divisors of n in count.
Input n.
Check if the number is equal to 1. If yes, print that 1 is neither prime nor composite and return from the program.
Create a for loop that iterates from 2 to n.
Within the loop, for every index, we will check whether n is divisible by i or not. If yes, increment count(number of divisors of n). Otherwise, continue with the next iteration.
After we come out of the loop, check the value of count. If it is equal to zero, it means that n can only be divided by 1 and itself. If it is more than zero, n is a composite number.
Print the results.

Below is the code for the same.

The below program checks whether the number is prime or not in the main method itself.

//C Program to check whether a number is prime or not
#include <stdio.h>
int main() 
{
    int n;        //Declare the nummber
    printf("Enter the number: ");
    scanf("%d",&n);    //Initialize the number
    if(n == 1){
        printf("1 is neither prime nor composite.");
        return 0;
    }  
    int count = 0;         //Declare a count variable
    for(int i = 2; i < n; i++)  //Check for factors
    {
        if(n % i == 0)
            count++;
    }
    if(count == 0)           //Check whether Prime or not
    {
        printf("%d is a prime number.", n);
    }
    else
    {
        printf("%d is not a prime number.", n);
    }
    return 0;
}

Enter the number: 5
5 is a prime number.

Method 2: Check whether a number is prime or not Using Function

In this method, we use a function to check whether a number is prime or not. This approach is similar to the above method. We pass the given number to a function. In the function, we use a for loop and check if the number is completely by any other number rather than 1 and the number itself.

Algorithm:

Declare variables n and count. Initialize count with 0. We will store the number of divisors of n in count.
Input n.
Check if the number is equal to 1. If yes, print that 1 is neither prime nor composite and return from the program.
Create a function isPrime() which takes an integer parameter and has return type bool.
Pass the given number to the function isPrime().
Create a for loop that iterates from 2 to n.
Within the loop, for every index, we will check whether n is divisible by i or not. If yes, increment count(number of divisors of n). Otherwise, continue with the next iteration.
After we come out of the loop, check the value of count. If it is equal to zero, it means that n can only be divided by 1 and itself. If it is more than zero, n is a composite number.
Return true if the number is prime, otherwise return false.
If isPrime() returns true, print that n is prime otherwise print that n is not prime.

Below is the code for the same.

The below program demonstrates how to check whether a number is prime or not using a function.

//C Program to check whether a number is prime or not using function
#include <stdio.h>
#include <stdbool.h>
bool isPrime(int n){
    int count = 0;         //Declare a count variable
    for(int i = 2; i < n; i++)  //Check for factors
    {
        if(n % i == 0)
            count++;
    }
    if(count == 0) 
        return true;
    return false;
}
int main() 
{
    int n;        //Declare the nummber
    printf("Enter the number: ");
    scanf("%d",&n);    //Initialize the number
    if(n == 1){
        printf("1 is neither prime nor composite.");
        return 0;
    }  
    if(isPrime(n))          //Check whether Prime or not
    {
        printf("%d is a prime number.", n);
    }
    else
    {
        printf("%d is not a prime number.", n);
    }
    return 0;
}

Enter the number: 67
67 is a prime number.

Method 3: Check whether a number is prime or not Using sqrt(n) Function

This approach is more efficient that the above approaches. The reason behind choosing sqrt(n) is that the smallest and the greatest factor of n can not be more than the sqrt(N). The moment we find any factor, we stop further execution of the loop.

Algorithm:

Declare a variable n.
Input n.
Check if the number is equal to 1. If yes, print that 1 is neither prime nor composite and return from the program.
Create a function isPrime() which takes an integer parameter and has return type bool.
Pass the given number to the function isPrime().
Create a for loop that iterates from 2 to sqrt(n).
Within the loop, for every index, we will check whether n is divisible by index or not. As soon as n is divided by index, we return false.
If the loop ends without n being divided by any index, it means it doesn't have more than 2 factors(1 and n). We return true.
If isPrime() returns true, print that n is prime otherwise print that n is not prime.

Below is the code for the same.

We pass n to a function and return true or false depending on whether the number is prime or not respectively.

#include <stdio.h>
#include <stdbool.h>
bool isPrime(int n){
    for(int i = 2; i < n; i++)  //Check for factors
    {
        if(n % i == 0)
            return false;
    }
    return true;
}
int main() 
{
    int n;        //Declare the nummber
    printf("Enter the number: ");
    scanf("%d",&n);    //Initialize the number
    if(n == 1){
        printf("1 is neither prime nor composite.");
        return 0;
    }  
    if(isPrime(n))          //Check whether Prime or not
    {
        printf("%d is a prime number.", n);
    }
    else
    {
        printf("%d is not a prime number.", n);
    }
    return 0;
}

Enter the number: 30
30 is not a prime number.

Method 4: Check whether a number is prime or not Using a recursive function

In this method, we use a recursive method to check whether a number is prime or not.

Algorithm:

Declare a variable n.
Input n.
Check if the number is equal to 1. If yes, print that 1 is neither prime nor composite and return from the program.
Create a function isPrime() which takes two integer parameters and has return type int.
Pass the given number, n and n / 2 to the function isPrime().
Within the function, for every index, we will check whether n is divisible by index or not. Here, index is the second parameter(n / 2).
We will check whether n is divided by any number from n / 2 to 2. As soon as n is divided by index, we return 0. Otherwise, we return (isPrime(n, i - 1). This means we are now checking for a lower number. So here, instead of a for loop, we are doing the same work using recursion.
The base case is that if i <= 1, we will return 1. If our index becomes 1 or less than 1, we return 1.
If isPrime() returns 1, print that n is prime otherwise print that n is not prime.

The below program demonstrates how to check whether a number is prime or not using a recursive function.

//c program to check whether a number is prime or not using recursive function
#include<stdio.h>
#include<stdlib.h>

int isPrime(int n, int i)   //Function Definition
{
    if (i <= 1){
        return 1;
    }
    else{
      if (n % i == 0)
         return 0;
      else
         return isPrime(n, i - 1);
    }
}
//Driver Code
int main()
{
    int n, flag;                        //Declare the variable
    printf("Enter a number: ");
    scanf("%d",&n);                      //Input the number
    if(n == 1){
        printf("1 is neither prime nor composite.");
        return 0;
    }  
    flag = isPrime(n, n / 2);   //Function Call
    if (flag == 1)             //Check whether prime or not
        printf("%d is a prime number.", n);
    else
        printf("%d is not a prime number.", n);
    return 0;
}

Enter a number: 5
5 is a prime number.

C TUTORIAL

C PROGRAMS

INTERVIEW TESTS

EXECUTE CODE

C++ TUTORIAL

C++ PROGRAMS

INTERVIEW TESTS

EXECUTE CODE

PYTHON TUTORIAL

PYTHON HOW TOS

INTERVIEW TESTS

EXECUTE CODE

JAVA TUTORIAL

JAVA CODE EXAMPLES

SPRING TUTORIAL

MORE IN JAVA

COMPUTER ARCHITECTURE

COMPUTER NETWORK

OPERATING SYSTEM

DBMS & SQL

PL/SQL

MongoDB

EXECUTE SQL

ANDROID DEVELOPMENT

GO LANGUAGE

LINUX

DOCKER

HTML TAGS (A to Z)

CSS REFERENCES

SASS/SCSS

KOTLIN

GAME DEVELOPMENT

PHP

GIT GUIDE

JAVASCRIPT

ADVANCED DSA

C Program To Check whether a number is prime or not

Method 1: C Program to Check whether a number is prime or not Using for loop

Algorithm:

Method 2: Check whether a number is prime or not Using Function

Algorithm:

Method 3: Check whether a number is prime or not Using sqrt(n) Function

Algorithm:

Method 4: Check whether a number is prime or not Using a recursive function

Algorithm: