1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Have you tried your code on some sample inputs? Does it seem to work? \$\endgroup\$ – svick Jun 6 '13 at 13:54
  • \$\begingroup\$ @svick yes it does work for all those that i tried \$\endgroup\$ – ragsvds Jun 6 '13 at 14:17
2
\$\begingroup\$
  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.
\$\endgroup\$
  • \$\begingroup\$ thanks a lot for ur response and for introducing me to the Sieve of Eratosthenes. \$\endgroup\$ – ragsvds Jun 6 '13 at 14:20
  • \$\begingroup\$ and thanks for taking the trouble to find all this... \$\endgroup\$ – ragsvds Jun 6 '13 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.