如果在Python中输入大数字时如何有效地找到范围内的完美正方形

Question

问题是当输入数字非常大时,如何有效地找到给定范围内的完美正方形.我的解决方案是Time Limit Exceeded错误.我已经检查了以下链接,但它们没有解决我的问题:
- 完美广场上的Python程序
- 我如何检查一个数字是否是一个完美的正方形？
- 确定整数的平方根是否为整数的最快方法(我不知道如何实现Python中此链接中给出的解决方案).

问题是:

输入格式:第一行包含T,即测试用例的数量.随后是T测试用例,每个测试用例都在换行符中.每个测试用例包含两个空格分隔的整数,表示A和B.查找A和B范围内的所有完美正方形(包括两者).

输入示例:

2
3 9
17 24

我写的代码是:

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