How to Check for given number is Prime or Not (Optimizing step by step)

General Algorithm:

for(i=2;i<n;i++)
{
if(n%2==0)
break;
}
if(i==n)
puts("Prime");
else
puts("Not Prime");

Better Solution:

for(i=2;i<n/2;i++) //perfect divisor will be less than n/2
{
if(n%2==0)
break;
}
if(i==n)
puts("Prime");
else
puts("Not Prime");


Even Better Solution:

int k = sqrt(n);
for(i=2;i<k;i++) //At least one factor will be less than square_root(n)
{
if(n%2==0)
break;
}
if(i==k)
puts("Prime");
else
puts("Not Prime");


Even more Better Solution:

if(n%2==0)
{
puts("Prime");
}
else
{
for(i=3;i<k;i+=2)
//if it is not divisible by 2, then no need to check for multiple of 2
{
if(n%2==0)
break;
}
if(i==k)
puts("Prime");
else
puts("Not Prime");
}