如何在Python中高效地找到指定范围内大数的完全平方数

Question

问题是如何高效地在输入的数字非常大时，在给定范围内找到完全平方数。我的解决方法导致“超时”错误。我已经查看了以下链接，但它们没有解决我的问题：
- 关于完全平方数的Python程序
- 如何检查一个数字是否为完全平方数？
- 确定一个整数的平方根是否为整数的最快方法（我不知道如何在Python中实现该链接中给出的解决方案）。

问题描述为：

输入格式：第一行包含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

虽然这段代码对于较小的数字是有效的，但对于大输入会出现“超时”错误。

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

- titan7585

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

- arshajii

---

你颠倒了floor和ceiling。而且在sqrt结果中需要小心四舍五入。 - Mark Ransom

@MarkRansom 谢谢，我已经纠正了地板/天花板的混淆。 - arshajii

在这里您会得到错误：>>> math.ceil(math.sqrt(17)) 5.0

math.floor(math.sqrt(24)) 4.0。

- Hackaholic

成功了。我只需要在该范围内的完全平方数的数量，因此通过找到 a = int(math.ceil(math.sqrt(x))) 和 b = int(math.floor(math.sqrt(x))) 然后 print (b + 1) - a 就完成了任务。 - titan7585

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

- Hackaholic

Answer 3

你的代码中有几个错误，比如numbers = map(int, raw_input().split())必须在循环外部。计数器counter=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

- Stefan Gruenwald