完全平方数的例子是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 ?
很容易注意到完美正方形之间的区别:
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 时,这可能会很慢。