首页 文章

什么是决定数字是否是Python 3中的平方数的最快方法

提问于
浏览 次
0

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

该列表需要多次检查，列表可以是 any positive integer ，这意味着整数可以是 very large ，实际上，对于使用涉及math.sqrt（）函数的 other 解决方案来说太大了，这会产生如下所示的溢出错误：

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

正如您所看到的，处理多个数字需要很长时间，这就是为什么我需要更快的方法 .

python list function math numbers

1 回答

  • 1

    一种简单的方法是编写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
    回复于

相关问题