python - 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

与其从Ato循环B并检查完美的正方形，不如直接遍历从sqrt(A)tosqrt(B)和平方的整数，给你答案。

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

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

因此，我们的答案是：

32 2 = 1024
33 2 = 1089
34 2 = 1156
35 2 = 1225
36 2 = 1296
37 2 = 1369
38 2 = 1444
39 2 = 1521
40 2 = 1600
41 2 = 1681
42 2 = 1764
43 2 = 1849
44 2 = 1936

Answer 2

这是我尝试过的：

>>> def isperferct_square(n):
...     return int(math.sqrt(n))*int(math.sqrt(n)) == n
... 
>>> isperferct_square(10)
False
>>> isperferct_square(9)
True
>>> isperferct_square(10000000000000000000)
False
>>> isperferct_square(112312424354957359732985732897583297592735932)
False
>>> isperferct_square(10000000000)
True
>>> 

Answer 3

您的代码中有几个错误，例如 numbers = map(int, raw_input().split()) 必须在循环之外。与计数器 = 0 相同。无论如何，这里有一个代码，它应该适用于非常高的整数：

t = map(int,raw_input().split())

def is_perfect_square(x):
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    n = int(x)
    if n == 0:
        return False
    a, b = divmod(n.bit_length(), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y

count = 0
for i in t:
    if is_perfect_square(i)**2 == i:
        count+=1

print count