Displaying Prime Numbers untill given limit

A number is a prime number if it is divisible only by  1 and itself

For E.x. 5 divisible by only 1 and 5, So Prime number;
         6 divisible by 1,2,3 and 6, So not Prime number



//displaying prime numbers until given limit
#include<stdio.h>
#include<math.h>

//The math.h header file provides square root "sqrt" built in function for us
main()
{
   int i , j , lim, c;
   printf("Enter a limit : ");
   scanf("%d",&lim);
   
   for(i=1;i<=lim;i++)
   {
       c=0;
       
       /*Since 2 is a Even prime number we can print it directly
          numbers greater than 2 are checked with logic*/
       if(i>2)
       {
           for(j=2;j<=sqrt(i);j++)
           {
               if(i%j==0)
               {

              /*If the number is divisible by other than 1 and itself this condition

                    holds true */
                   c=1;
                   break;
               }
           }
       }
       if(c!=1)
           printf("%d\n",i);
   }
}

NOTE :

Look at the for loop which has a condition  j<= sqrt(i).This is to reduce time Complexity. Actually the condition can be like this too j< = i .In both cases the program runs successfully but in terms of time complexity square-root(i) is best .

For Example,

    Lets us take num = 4 ,

                 (i)  j<=4. So it takes 4 iterations to complete the for loop.

                 

                 (ii)  j<=sqrt(4) => j<=2 , So it takes 2 iterations to complete the for loop.

When we see 4 and 2 there is no much difference Right?.

But what about in case

         

                           num = 1024

Then

                            (i) j<= 1024, So it takes 1024 iterations to complete the for loop.

                            (ii) j<=sqrt(1024) => j<=32 ,So it takes 32 iterations to complete the for loop.

     Just 32 iterations it take  to complete the program while the former takes 1024 iterations.So sqrt(i) is best.

Please comment below if you have any Doubts,

Want to learn more about Time complexity ?

Then visit the link below ,a nice video

https://www.youtube.com/watch?v=FEnwM-iDb2g