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

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