检查数字是否为完全平方
我如何检查一个数字是否是一个完美的平方？
就目前而言，速度并不重要，只关心工作。
回答 21
Stack Overflow用户
发布于 2010-03-22 09:20:45
依赖任何浮点计算(math.sqrt(x)或x**0.5)的问题是，您不能真正确保它是准确的(对于足够大的整数x，它不会准确，甚至可能溢出)。幸运的是(如果你不着急；-)有很多纯整数方法，比如下面这样：
def is_square(apositiveint):
x = apositiveint // 2
seen = set([x])
while x * x != apositiveint:
x = (x + (apositiveint // x)) // 2
if x in seen: return False
seen.add(x)
return True
for i in range(110, 130):
print i, is_square(i)提示:它基于平方根的“巴比伦算法”，见wikipedia。它确实适用于任何正数，对于这些正数，您有足够的内存进行计算；-)。
编辑：让我们看一个例子...
x = 12345678987654321234567 ** 2
for i in range(x, x+2):
print i, is_square(i)这将根据需要打印(并在合理的时间内打印；-)：
152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False在您提出基于浮点中间结果的解决方案之前，请确保它们在这个简单的示例中正确工作-- it's hard (您只需要额外检查几次，以防sqrt计算出的结果有一点偏差)，只是需要一点小心。
然后尝试使用x**7并找到解决问题的聪明方法，
OverflowError: long int too large to convert to float当然，随着数字的不断增长，你必须变得越来越聪明。
如果我赶时间，当然，我会使用gmpy --但是，我显然是有偏见的；-)。
>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0是的，我知道，这太容易了，感觉就像作弊(有点像我对Python的感觉；-) --一点也不聪明，只是完美的直接和简单(在gmpy的情况下，纯粹的速度；-)……
Stack Overflow用户
发布于 2010-03-22 09:26:44
使用牛顿的方法快速地将最接近的整数平方根归零，然后将其平方，看看它是否是你的数字。参见isqrt。
Python≥3.8有math.isqrt。如果使用的是较旧版本的Python，请查找"def isqrt(n)“实现here。
import math
def is_square(i: int) -> bool:
return i == math.isqrt(i) ** 2Stack Overflow用户
发布于 2010-03-22 09:39:50
由于在处理浮点计算(例如这些计算平方根的方法)时，您永远不能依赖精确的比较，因此一种不太容易出错的实现是
import math
def is_square(integer):
root = math.sqrt(integer)
return integer == int(root + 0.5) ** 2假设integer是9。math.sqrt(9)可以是3.0，但也可以是2.99999或3.00001，所以直接平方结果并不可靠。知道int取底值，首先将浮点值增加0.5意味着，如果我们在一个范围内，float仍然有足够好的分辨率来表示接近我们要查找的数字，那么我们将得到我们要查找的值。
https://stackoverflow.com/questions/2489435
复制相似问题
腾讯云开发者
