How to check whether a Number is Prime Number

 Prime numbers are the numbers greater than 1 which are divisible only by 1 and itself, like 3 is divisible by 1 and 3 only. So, if a natural number n is a prime number, then it is divisible by only 1 and n and not divisible by any number from the sequence 2, 3, 4, ….. , (n - 1).

To check whether a number (n) is prime or not, check whether number n is multiple of any integer between 2 and √n. If there exist such a number then n is not a prime number, otherwise n is a prime number.

Algorithm:

1. Let the number to checked is n and i be any temporary number.
2. Set i = 2.
3. Check whether i is less than or equal to square root of n.
4. If no, then n is a prime number, otherwise move to step 5.
5. Check whether number n is multiple of number i.
6. If yes, number n is not a prime number, otherwise move to step 7.
7. Increment the value of i by 1 and move to step 3.

Instructions:

1. You need following two header files for this program to work.
   

   #include <stdio.h>
   #include <math.h>

2. Now ask the user to enter a number which he/she wants to check.
   

   int num, temp;
   printf("Enter the number you want to check : ");
   scanf("%d", &num);

3. Now if the input number is 1, it is not prime number else call function isPrime (function to check primality of a number) and if the function returns 1, the number is prime else number is not prime.
   

   int isPrime(int);
   if(num == 1)
       temp = 0;
   else
       temp = isPrime(num);
   if(temp == 1)
       printf("%d is a prime number", num);
   else
       printf("%d is not a prime number", num);

4. In function isPrime using an integer i (initially set to 2) in a while loop, check whether the number i divides perfectly the number input by user or not and return 0 if it divides otherwise increment the value of i and keep on checking untill the value of i becomes larger than square root of input number. So, if no number from 2 to √n divides perfectly the input number, then the number is prime.
   

   int isPrime(int num)
   {
       int i = 2;
       while(i <= sqrt(num))
       {
           if(num % i == 0)
               return 0;
           else
               i++;
       }
       return 1;
   }

Here are some screenshots of the working of sample program.

Check Prime Number using C

Check Prime Number using C

Check Prime Number using C

Check Prime Number using C

You can download the sample code from here.