Prime Number Program in C

Write a prime number program in C. In this tutorial, we are going to 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.

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.

Prime Number Program in C

Prime Number Program in C

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 in C

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.

Prime Number Program in C

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.

About WebRewrite

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