Two squares or not two squares - constant time optimization I have been trying to solve this problem, and after a bit of googling, I realised a \$O(\sqrt{n})\$ time complexity works fine (though the algorithm suggested is different from that I have used). My algorithm is as follows (pseudo code):

for i in range(sqrt(n/2+1)):
    if n-i*i is a perfect square:
        return True
return False


The exact code is as follows:

#include&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;
#include&lt;math.h&gt;
#define MAX 100000000
typedef unsigned long long int llu;
int isSquare(llu n){
    if(n%16!=0 &amp;&amp; n%16!=1 &amp;&amp; n%16!=9 &amp;&amp; n%16!=4)
        return 0;//as a square can only be of the form 16n+r ,where r belongsto {0,1,4,9}
    //The above step prevents use of expensive function sqrtl() in 75% cases
    llu root = sqrtl(n);
    return root*root == n;
}
int isSqSum(llu n){
    if(n%4==3)//as sum of two squares cannot be of the form 4n+3
        return 0;
    llu i;
    for(i=0;i*i&lt;n/2+1;++i)
        if(isSquare(n-i*i)) 
            return 1;
    return 0;
}
int main()
{
    int c ;
    scanf("%d",&amp;c);
    llu n;
    while(c--){
        scanf("%llu",&amp;n);
        if(isSqSum(n))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
} 


As you can see, I have already applied most of the optimizations I could think of, but I still keep getting TLE. Is there something wrong with my code or is it that the algorithm that I am using has a large constant of proportionality in time complexity?
llu root = sqrtl(n); is not safe.  The precision of a long double is not specified by C to give the exact correct answer for all unsigned long long.
Not sure yet why you get TLE (Time Limit Exceeded).  As the page you point to only has 10 small integers to test, there must be horribly wrong with your compilation or yu have an unstated interesting input.
Spent 30 minutes tracking down a bug because I forgot to a braces when extending the following.  Instead, highly reccomend to add breaces in all for(), if(), etc. except maybe in the the most trivial circumstance.

for(i=0;i*i&lt;n/2+1;++i)
  if(isSquare(n-i*i)) 
    return 1;

// Better
for(i=0;i*i&lt;n/2+1;++i) {
  if(isSquare(n-i*i)) {
    return 1;
  }
}