python - 当 Python 中的输入量很大时如何有效地找到一个范围内的完美平方

Question

问题是当输入非常大时，如何在给定范围内有效地找到完美平方。我的解决方案是给出 Time Limit Exceeded 错误。我已经检查了以下链接，但它们没有解决我的问题:
- 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 (我不知道如何在 Python 中实现此链接中给出的解决方案)。

题目问题是:

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).

输入示例:

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

虽然此代码适用于较小的数字，但对于较大的输入会出现 Time limit exceeded 错误。

(注意:gmpy 不是一个选项，因为代码必须在没有 gmpy 模块的在线编译器上运行)

Answer 1

与其从 A 循环到 B 并检查完美平方，为什么不循环遍历从 sqrt(A) 到sqrt(B) 和平方，给出你的答案。

例如，让我们求出 1000 到 2000 之间的平方数:

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

因此，我们的答案是:

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