How to find perfect squares in a range efficiently when the inputs are large numbers in Python
Question: The question is how to find perfect squares in a given range efficiently when
the inputs are very large numbers. My solution is giving `Time Limit Exceeded`
error. I have already checked the following links, but they didn't solve my
problem:  
\- [Python Program on Perfect
Squares](http://stackoverflow.com/questions/17508859/python-program-on-
perfect-squares)  
\- [How could I check if a number is a perfect
square?](http://stackoverflow.com/questions/2489435/how-could-i-check-if-a-
number-is-a-perfect-square)  
\- [Fastest way to determine if an integer's square root is an
integer](http://stackoverflow.com/questions/295579/fastest-way-to-determine-
if-an-integers-square-root-is-an-integer) (I have no idea how to implement the
solution given in this link in Python).

The problem question is:

> Input Format: First line contains T, the number of testcases. T test cases
> follow, each in a newline. Each testcase contains two space separated
> integers denoting A and B. Find all the perfect squares in the range A and B
> (both inclusive).

Example of an input:

    
    
    2
    3 9
    17 24
    

The code I wrote is:

    
    
    import math
    def is_perfect_square(n):
        return n % n**0.5 == 0
    
    t = int(raw_input())
    for i in range(t):
        numbers = map(int, raw_input().split())
        count = 0
        for j in xrange(numbers[0], numbers[1] + 1): # I also tried range() which gave memory error
            if (is_perfect_square(j)):
                count = count + 1
    
        print count
    

While this code is working for smaller numbers, it is giving `Time limit
exceeded` error for large inputs.

(NOTE : `gmpy` is not an option as the code has to be run on an online
compiler which does not have the `gmpy` module)


Answer: Instead of looping from `A` to `B` and checking for perfect squares, why not
just loop through the integers from `sqrt(A)` to `sqrt(B)` and square each,
giving you your answer.

For example, let's find the square numbers between 1000 and 2000:

    
    
    sqrt(1000) = 31.6  -->  32  (need the ceiling here)
    sqrt(2000) = 44.7  -->  44  (need the floor here)
    

Therefore, our answer is:

    
    
    322 = 1024
    332 = 1089
    342 = 1156
    352 = 1225
    362 = 1296
    372 = 1369
    382 = 1444
    392 = 1521
    402 = 1600
    412 = 1681
    422 = 1764
    432 = 1849
    442 = 1936
    

