Finding prime number with less time complexity

This is a program to find the number is prime or not with less time complexity.

step 1: Find the modulus of the number by 2 [To find its even or not]

step 2: Find the square root of that number(given)

step 3: Check the number with loop until the square root of that number.

Normal Time complexity : N power(n-1)

But using this program : the complexity is less that half of (N/2 power(n-1)/2)

#include
main()
{
int i,n,m,s=0;
system("clear");
printf("Enter the number : ");
scanf("%d",&n);
m=n;
if (n%2==0)
{
printf("The Number(%d) is not Prime",m);
s=1;
}
else
{
n=sqrt(n);
if ((n*n)==m)
{
printf("The number(%d) is not prime!",m);
s=1;
}
else
{
for(i=3;i<=n;i++)
{
if (n%i==0)
s=1;
}
}
}
if (s==1)
printf("The number(%d) is not prime!",m);
else
printf("The number is Prime!");
}