首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >在Python 3中,判断一个数字是否为平方数的最快方法是什么

在Python 3中,判断一个数字是否为平方数的最快方法是什么
EN

Stack Overflow用户
提问于 2018-06-10 03:04:11
回答 1查看 651关注 0票数 1

我试图根据列表中的数字是否是平方数来返回True/False输出。

该列表将需要检查几次,并且该列表可以是任何正整数,这意味着该整数可以是非常大的,实际上,对于涉及math.sqrt()函数的其他解决方案的使用来说,该解决方案太大了,这些解决方案会产生如下所示的溢出错误:

userList = [1*10**1000]
print ([x for x in userList if math.sqrt(x).is_integer()])

>>>Traceback (most recent call last):
print ([x for x in userList if math.sqrt(x).is_integer()])
OverflowError: int too large to convert to float

下面是我的*方法:

def squares():
    for i in userList:
        if i in squares: #the list in which all the square numbers are stored
            return True
        else:
            return False

*我目前的想法是将平方数预先准备到一个单独的列表中,以便进行比较,但我正在寻找一种替代方法,更快的方法,因为userList可能会变得非常大。

我希望将返回的输出存储在单独的列表中,如下所示:

out = []
for i in userList:
    out.append(squares())

print(out)
>>>[False,True...]

正如你所看到的,当处理许多数字时,这将需要很长的时间,这就是为什么我需要更快的方法的原因。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2018-06-14 00:17:17

一种简单的方法是编写一个integer square root函数。这是一种基于二进制搜索的次优(但仍然相当快)的方法:

def is_sqrt(m,n):
    return m**2 <= n < (m+1)**2

def isqrt(n):
    low = 0
    high = n
    m = (low + high)//2

    while not is_sqrt(m,n):
        if m**2 < n: #too small! must be in [m+1,high]
            low = m+1
        else: #too big! must be in [low, m-1]
            high = m - 1
        m = (low + high) // 2
    return m

def is_square(n):
    return n == (isqrt(n))**2

然后,以下内容几乎是瞬间完成的:

>>> is_square(77**200)
True
>>> is_square(77**200 + 1)
False
票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/50777577

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档