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

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

Subscribe Our Tutorials

Print Fibonacci series

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).

METHOD 2

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

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)).

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

### 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.