提问者:小点点

高效计算非常大的数字(如 10**20)的所有完美平方数


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

我们如何计算非常大的数字(如 10 pow 20)的所有完美平方数。对于 10 pow 20,有 10 pow 10 完全平方数。

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

蛮力:计算范围 1 到 10 的 x**2 pow 10。因为我的系统只接受 10 个 pow 6。这行不通。

两指针方法:我取了上限和下限。

上限为 10 pow 20

下限为 1

现在,我采取了两个指针,一个在开头,另一个在结尾。那么下限的下一个完美平方将是

下限(下限)*2 1)

示例:对于 4 下一个完美正方形是

4 (sqrt(4)*2 1)= 9

以同样的方式,上限将减少

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

示例:对于 25,前一个完全平方是

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

上述两种方法都不起作用,因为上限是非常非常大的数字 10 pow 20。

我们如何在更短的时间内有效地计算所有完美的平方直到 10 pow 20 ?


共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 时,这可能会很慢。