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
- How could I check if a number is a perfect square?
- Fastest way to determine if an integer's 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 1

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