高效计算非常大的数字（如 10**20）的所有完全平方数

Question

完全平方数的例子是1,4,9,16,25....

我们如何计算非常大的数字（如 10 pow 20）的所有完全平方数。对于 10 pow 20，有 10 pow 10 完全平方数。

到目前为止我做了什么....

Bruteforce：计算 1 到 10 pow 10 范围内的 x**2。因为我的系统只接受 10 pow 6。这没有用。

双指针方法：我已经采用了上限和下限....

上限是 10 pow 20

下限为 1

现在，我有两个指针，一个在开头，一个在结尾。那么下界的下一个完美平方将是

下限 + (sqrt(下限) *2+1)

示例：对于 4，下一个完全正方形是

4 + (平方(4)*2+1)= 9

以同样的方式上限将减少

上限 - (sqrt(上限) *2-1)

示例：对于 25，上一个完全平方是

25 - (sqrt(25)*2-1) =16

上述两种方法都效果不佳，因为上限非常大，10 pow 20。

我们如何才能在更短的时间内有效地计算出 10 pow 20 之前的所有完美平方？

Answer 1

很容易注意到完美正方形之间的区别：

0   1   4   9   16   25   ...
|___|___|___|___|_____|
  |   |   |   |    |
  1   3   5   7    9

所以我们有：

answer = 0;
for(i = 1; answer <= 10^20; i = i + 2)
    answer = answer + i;
    print(answer);
}

因为你想要直到x的所有完美平方，所以时间复杂度将是O(sqrt(x))，对于x = 10^20，它的平方是10^10，这可能会很慢。

Efficiently computing all the perfect square numbers for very large numbers like 10**20