Find perfect squares between two numbers The following problem is from codechef.com:


  Recently Chef become very much interested in perfect squares. We all
  know Chef and his weird interests. Anyways Chef will be soon writing
  his masters thesis on perfect squares revealing what-not-known
  properties of perfect squares. While doing his research, he happened
  to be confronted with some interesting perfect squares. These prefect
  squares consists only of digits which are themselves perfect squares.
  0, 1, 4 and 9 are such digits. These are called perfect digits.
  
  As we all know Chef also has habit of asking too many questions, he is
  asking- given two numbers a and b, how many perfect squares exists
  between these two numbers inclusive, that contains only perfect
  digits.
  
  Input:
  
  First line of input will contains T, number of test cases. Then T
  lines follows, each containing two positive integers a and b.
  
  Constraints:
  
  
  \$T \le 500\$
  \$1 \le a \le b \le 10000000000\$
  
  
  Output:
  
  For each input, output number of perfect digit squares between given
  numbers. 
  
  Sample:
  
  Input:

2
1 10
100 10000
 Output:

3
9



How can I decrease the running time of my solution?

#include&lt;stdio.h&gt;
int main()
{
    int test;
    long long int num1,num2,start,stop,i,j,square,rem;
    scanf("%d",&amp;test);
    while(test--)
    {
        long long int count=0;
        scanf("%lld%lld",&amp;num1,&amp;num2);
        start=sqrt(num1);
        stop=sqrt(num2);
        for(i=start;i&lt;=stop;i++)
        {
            square = i*i;

            if(square&lt;num1)
            {
                continue;
            }
            else
            {
                while(1)
                {

                    rem=square%10;
                    if(rem!=1 &amp;&amp; rem!= 4 &amp;&amp; rem!=9 &amp;&amp; rem!=0 )
                    {
                        break;
                    }
                    if(square&gt;=10)
                    {
                        square=square/10;

                    }
                    else
                    {
                        if(square!=1 &amp;&amp; square!= 4 &amp;&amp; square!=9 &amp;&amp;square!=0 )
                        {
                                break;
                        }
                        else
                        {
                            count+=1;
                        }
                        break;
                    }
                }
            }
        }
        printf("%lld\n",count);
    }
    return 0;
}
I didn't have a very close look at your solution, but a simple (algorithm-agnostic way) to improve efficiency for this kind of task, is to cache (think about which data structure would suit this task) previously found solutions. For instance consider test 1 being a=1, b=10000 and test 2 exactly (or almost) the same, like for instance a=1 and b=10000 or a=2 and b=9999. You are going to check recompute the whole thing, although you just did that.

p.s.: I'll have a closer look at it if you are still struggling with it when I get home.