C Programming Reference >> C Programming Short Notes >>

28/05/07 - 750 Views - Ratings :   4.25 of 5 / 4 Votes

Simple C program to find wether a number is prime or not

Level - Begineer

In mathematics a positive number is called prime number if and only if it has exactly two factors, 1 and number itself.

There is only one even prime number 2 since rest all even numbers have two as a divisor.

There exist infinite number of prime numbers. Also prime numbers are randomly distributed with no given pattern even though mathematician tried to map it but till now no formulae is devised to calculate the sequence of prime numbers.

Now thier can be a large number of ways in which a program can check wether a number is prime or not but not all of them are not efficient. Below we will try to come up with algortihm which is simple yet most effective in implementation and optimize to perform the best. Since as size of the number being tested increases the number of calculation also increases drasticaly so complexity and efficiency of algorithm used do matter.

Limitation factor can be variable size range and processing time.

Logic 1: Well to test wether n is a prime number we can try to find remainder with all numbers less than n using a loop and if we find a number which divides perfectly that is % give value 0 we can break the loop and say that number is not prime. If loop doesnot end by break statement but by succesfull loop termination then number is prime. In worst case the number is a prime number their will n comparisons.

Logic 2: Improvement in Logic 1. It is observed that divisor of number is never greater than square root of that number so we can check only the values which are smaller than than the square root. So number of comparison for number n becomes n^1/2 + squareroot calculation algortihm complexity in worst case.

Logic 3: Improvement in Logic 2. Now calculating a square root at higher values has its own growth function for complexity and involve unecessary decimal calculation. So we use a derived property which involves only integer calculation we continue calculation only when quotient of the divison is greater than divisor under such a case worse case compelxity becomes n/2 +n/2 = n which infact equal to Logic 1 but in a average case it performs much more optimally.

Now we create a subroutine which returns 0 (false) if number is not prime and 1 or other value (true) if number is prime, number to be checked is send as parameter.

Also note that this function also becomes too complex when value passed is large as number of comparison to be perform increases.

Source code below is written in C and is implementation of logic above and shows, how to determine the number is a prime or not .

#include <stdio.h>
#include <conio.h>

int checkprime (int num)


{
  int counter = 2;
  while (1)
   {
    if (!(num %  counter)) return 0; //Divisor found hence number is not prime.
    if ((num/counter) < counter) return counter; //No Divisor Found
    counter ++;
   }
}

int main ()

{
 int num;
 clrscr ();
 
 printf ("\n\nEnter Number To Be Checked : ");
 scanf ("%d", &num);
 
 if (checkprime (num))
  {
    printf ("\n\n %d Is A Prime Number. ",num);
  }
 else
  {
    printf ("\n\n %d Is Not A Prime Number.", num);
  }
 getch ();
 return 0;

}

Reader Comments -

Add Comments 


Name :    

Reply :   


Rating :  
              5 - Excellent
              4 - Good
              3 - Average
              2 - Poor
              1 - Useless
          
Code :