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.
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
C Program to Print Prime Numbers from 1 to N
Program to implement a stack using an array
How 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).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
function isPrime(int n) { /* If a number is less than or equal to 1, then it's not a prime */ if(n <= 1) { return false; } //Run a loop from 2 to n-1 for( i = 2; i < n; i++) { /*If it's divisible by any other number, *then it's not a prime number */ if(n%i == 0){ return false; } } return true; } |
METHOD 2 –
This approach is better than the first approach, as we run a loop from 2 to n/2.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
function isPrime(int n) { /* If a number is less than or equal to 1, then it's not a prime */ if(n <= 1) { return false; } //Run a loop from 2 to n/2 for( i = 2; i <= n/2; i++) { /*If it's divisible by any other number, *then it's not a prime number */ if(n%i == 0){ return false; } } return true; } |
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)).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
function isPrime(int n) { /* If a number is less than or equal to 1, then it's not a prime */ if(n <= 1) { return false; } //Run a loop from 2 to n/2 for( i = 2; i <= sqrt(n); i++) { /*If it's divisible by any other number, *then it's not a prime number */ if(n%i == 0){ return false; } } return true; } |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <stdio.h> #include <math.h> int checkPrime(int n) { /* Run a loop from 2 to sqrt(n) */ for (int i=2; i <= sqrt(n); i++){ /* Check if it is divisible */ if(n%i == 0){ return 0; } } return 1; } int main() { int n; printf("Enter a number \n"); scanf("%d", &n); //If number is greater than equal to 2 if(n >= 2 && checkPrime(n)){ printf ("Input number is a Prime number"); } else { printf("Input number is not a prime number"); } return 0; } |
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.
