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.

C Program to Check whether a number is prime or not

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

Subscribe Our Tutorials

Get Latest Updates on Facebook

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.

About WebRewrite

I am technology lover who loves to keep updated with latest technology. My interest field is Web Development.
Tagged , . Bookmark the permalink.