Square free Integer

Question

I am an amateur programmer and I tried coding this problem using the TurboC++ IDE (though my code is in C), but the site's compiler throws a "TIME LIMIT EXCEEDED" error. How can I optimize my code further?

#include<stdio.h>
#include<math.h>
int main()
{
    long int n,j,k,sqt,tot,t,i,c;

    scanf("%ld",&t);
    for(i=0;i<t;i++)
    {
        scanf("%ld",&n); tot=n;
        for(k=1;;k++)
        {c=0;
            for(j=k;j>=2;j--)
            {
                if((k%j)==0)
                { if(((long)sqrt(j)*(long)sqrt(j)!=j))
                    {c=0;}
                else {c++;break; }
                }
            }
            if(c==0)
            {tot--;}
            if(tot==0)  {printf("%ld\n",k);break;}
        }
    }

    return 0;
}

Please do tell me if the code is wrong.

Answer 1

1. You need to pre-calculate all square-free integers below the greatest in input (in test it's 100) and don't calculate that for every input value.
2. You need a very fast precalculation algorithm like a modified Sieve of Eratosthenes.

3. Don't forget about the time limit - it's 8 sec. only (and not on the top hardware, I assume). Benchmark your code using the following testcase:

   1
   10000000
   

4. If you want to find past solutions, take it here.

5. If you want to see the explanation, read this topcoder editorial about the problem SquareFree.