Program to find whether a number is prime or not

A prime number is one which is only divisible by itself or 1 and not by any other number.
Series of Prime numbers is given below
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ...  
The only even prime number is 2.

we can check for prime number by checking whether it is even or not. If it is not even, then we can set a loop to check it with series of odd numbers

Let 'n' be the given number
if(n==2)
{
it is prime;
return ; stop the program
}
if (n%2==0)
{
it is not prime
return ; stop the program
}
flag=0
for(i=3; i<n; i=i+2)
{
if ((n%i)==0)
{
then number is not prime because it is completely divisible by number other than itself or 1.
flag =1
break from loop; 
}
}
if flag == 0 then number is prime
else it is not prime

For example take given number =11
11 !=2
11%2 !=0
value of i    computation       loop count
3                   11%2 != 0            1
5                   11%3 != 0            2
7                   11%4 != 0            3
9                   11%5 != 0            4

Hence 11 is prime.

Let us take another example n=9
9 != 2
9%2 != 0
value of i       computation      loop count
3                      9%3 ==0             1     set flag to indicate number not prime break from loop
9 is not prime
 
We can even enhance above algorithm because there is certainly something it is checking twice
For example, we take the given number to be 11
11%2!=0 this means the given number is odd
multiplication of two odd numbers result in a odd number
odd*odd =odd (always)
even*odd=even (always)
even*even=even (always) 

Now we have to check if 11 is completely divisible by odd number series (excluding 1) less than 11. i.e { 3,5,7,9 }
if 11 is not prime then
multiplication of any two values in set {3, 4, 7, 9} should make 11.
for example
either
3*3 should be 11
or
3*5 should be 11
or
3*7 should be 11
or
3*9 should be 11
or
5*5 should be 11
or
5*7 should be 11
and so on ........
but none are
so 11 is Prime
Now we shouldn't be bothered to check for value above 3*3 because 3*3 is 9 and 3*5= 15 (we see 3*4 is 12 ) so we know 3*3 is the best we need to check if the number is prime.

lets take n= 53
we check if its 2, but  it is not.
we check if it is divisible by 2, it is not. Hence is it odd.
we check it with odd number series excluding 1
3, 5, 7, 9, 13.....
 3*3<=53 ( 53%3!= 0)
5*5<=53  ( 53%5!= 0)
7*7<=53   (53%7!= 0)
9*9>53  Stop here
we can stop here and we can say number is prime

let us take n=49
we check if its 2, but  it is not.
we check if it is divisible by 2, it is not. Hence is it odd.
we check it with odd number series excluding 1
3, 5, 7, 9, 13.....
3*3<=49 (49%3!=0)
5*5<=49  (49%5!=0)
7*7<=49  (49%7==0)
Number is not prime.

It can be seen that square root of given number can be limit of our test of whether number is prime or not.

 #include<stdio.h>
#include<math.h>
int main()
{
        int n;
        int i;
       float nsqrt;
       int flag=1;

       printf("\nEnter a number:");
       scanf("%d",&n);

       if(n==2)
              {
               printf("\n%d is Prime",n);
               return 0;
              }
         if(n%2==0)
             {
               printf("\n%d is not Prime",n);
               return 0;
             }
        else
            {
              nsqrt=sqrt(n);
              for(i=3;i<=nsqrt;i+=2)
                   {
                      if(n%i==0)
                             {
                                 printf("\n%d is not prime",n);
                                  flag=0;
                                   break;
                               }
                       }
                     if(flag==1)
                           printf("\n%d is prime",n);
               }
                return 0;
}