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

Write a c program to check whether a number is prime or not. In this tutorial, we are going to write a c program to check whether an input number is prime or not.

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

This type of problem is mainly asked in an interviews.

Interview questions

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.

C Program to Print Prime Numbers from 1 to N

Print Fibonacci series in PHP

Subscribe Our Tutorials

Program to implement a stack using an array

## 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 first and second method. 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

We have discussed three approaches to check whether an input number is prime or not. Let’s write a C code 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.
In this video tutorial, I have explained the algorithm to check whether a number is prime or not. 