Python - 在给定的大数范围内查找所有完全平方数的最快方法

Question

我想写一个方法，在Python中获取给定范围内的所有完美平方数。例如在2621163和520001400002之间的大范围内。现在很明显，通过迭代范围并检查一个数字是否是完美的，可以实现如下：

def is_square(n):
    return math.sqrt(n).is_integer()

对于大范围的计算，直接输出结果是很愚蠢的（小范围可以运行得很好），并且需要很长时间。我想知道是否有一些 Python 魔法或数学魔法（比如修改后的裴蜀定理），可以用来解决这个问题。

编辑：此外，我正在使用 Python 3.X，所以可以使用大整数。

- Vrashabh Irde

Answer 1

您可以简单地找到在指定范围内具有平方的最小和最大数字。然后，您可以返回该范围内每个数字的平方。

import math

def perfect_squares(min, max):
    lowest = int(math.ceil(math.sqrt(min)))
    highest = int(math.sqrt(max))
    return (n**2 for n in range(lowest, highest + 1))

- grc

Answer 2

你会发现，如果你知道最接近的完全平方数的第一个和最后一个，那么它们之间的范围就是所有完全平方数。我会这样计算：

import math

def all_squares(a,b):#a is the starting point whereas b is the end of range
    smallest = int(math.ceil(math.sqrt(a)))#perfect square closest to lower bound (rounded up)
    largest = int(math.sqrt(b))#perfect square closest to upper bound (rounded down)
    squares = []
    for s in range(smallest, largest+1):
        squares.append(s**2)
    return squares

- Zulqarnain Khan

Answer 3

不使用函数的简单Python代码

import math
num=500
for i in range(1,math.ceil(math.sqrt(num))):
    print(i*i)

- Rohit

Answer 4

使用numpy获取1到100之间的完全平方数

import numpy as np

a={int(np.sqrt(x)) for x in range(1,101)}

b= np.power(list(a),2) 

print(a)

print(b)

- Sonu Sharma

Answer 5

def perfect_squares(start, stop):
  return (i*i for i in xrange(math.ceil(math.sqrt(start)), math.floor(math.sqrt(stop)) + 1))

- Itay Karo

Answer 6

假设数字是34929456，你可以知道它不是一个完全平方数，因为当它被分成3：4：9：2：9：4：5：6 = 42时。42不是一个平方数，这意味着34929456不是一个完全平方数！（我没有使用计算器）现在我们知道它不是一个完全平方数，您将四舍五入...... 因此，您需要最后两位数字，即56！要使56成为单个数字，请使用7（次）8= 56！34929456是一个8位数，这意味着8-7 = 1 + 4 = 5。因此，答案在5000和6000之间。现在，您进行一些猜测。让我们尝试5500的平方= 30250000。所以我们知道平方根稍微大一些！现在让我们尝试5910。5910平方= 34928100。所以现在我们知道答案在5910和5911之间！谢谢阅读！希望对您有所帮助！

- Hussain

---

完全平方数（PS）的各位数字之和不一定是一个完全平方数，例如64、256。 - Vishal K