Write a c program to check whether a number is prime or not. Given an integer, We have to write an efficient code to check whether a number is prime or not.

**What is a Prime Number?**

A prime number is a natural number **greater than 1** that has no positive divisors other than 1 and itself.

**NOTE** – Two (2) is the only even prime number.

For example – 3, 5, 7, 13 is a prime number, as it’s divisible by 1 and itself. Similarly, 17, 19 etc. are also prime numbers.

6 is not a prime number as it’s divisible by 1, 2, 3 and 6.

Program to print prime numbers from 1 to n using sieve algorithm

Program to implement a stack using an array

## Algorithm to Check Whether a Number is Prime or Not

**METHOD 1** –

Run a loop from 2 to n-1 (where n is a number) and check whether a number is perfectly divisible by any other number other than 1 and itself. If it’s divisible by any other number other than 1 and itself then it’s not a prime number.

The time complexity of this approach is O(n).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | function isPrime(int n) { /* If a number is less than or equal to 1, then it's not a prime */ if(n <= 1) { return false; } //Run a loop from 2 to n-1 for( i = 2; i < n; i++) { /*If it's divisible by any other number, *then it's not a prime number */ if(n%i == 0){ return false; } } return true; } |

**METHOD 2 ** –

This approach is better than the first approach, as we run a loop from 2 to n/2.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | function isPrime(int n) { /* If a number is less than or equal to 1, then it's not a prime */ if(n <= 1) { return false; } //Run a loop from 2 to n/2 for( i = 2; i <= n/2; i++) { /*If it's divisible by any other number, *then it's not a prime number */ if(n%i == 0){ return false; } } return true; } |

**METHOD 3 **–

This approach is much better than the method 1 and 2. In this approach, we run a loop from 2 to sqrt(n).

The time complexity of this approach is O(n^(1/2)).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | function isPrime(int n) { /* If a number is less than or equal to 1, then it's not a prime */ if(n <= 1) { return false; } //Run a loop from 2 to n/2 for( i = 2; i <= sqrt(n); i++) { /*If it's divisible by any other number, *then it's not a prime number */ if(n%i == 0){ return false; } } return true; } |

We have discussed three approaches to check whether a number is prime or not. The third approach is the most efficient one, let’s implement it through a code.

## C Program to Check Whether a Number is Prime or Not

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <stdio.h> #include <math.h> int checkPrime(int n) { /* Run a loop from 2 to sqrt(n) */ for (int i=2; i <= sqrt(n); i++){ /* Check if it is divisible */ if(n%i == 0){ return 0; } } return 1; } int main() { int n; printf("Enter a number \n"); scanf("%d", &n); //If number is greater than equal to 2 if(n >= 2 && checkPrime(n)){ printf ("Input number is a Prime number"); } else { printf("Input number is not a prime number"); } return 0; } |

### Conclusion

I have explained three approaches with their time complexity. If you know some other most efficient method to solve this problem then you can let us know through your comments.