如何找到两个数字之间的整数平方
how to find whole squares between 2 numbers
我想求出两个数 A、B 的完全平方（数字可以是 positive/negative）。我也想实现 O(sqrt(abs(B))).
的时间复杂度
我为此编写了以下代码：
count = (int)(Math.floor(Math.sqrt(Math.abs(B)) - Math.ceil(Math.sqrt(Math.abs(A))) + 1);
这通常运行良好，但当范围在 -ve 和 +ve 数字之间时失败。
例如范围是A = -1, B = 1。那么我认为它应该是return 2 (0, 1) 但是returns 1.
我在SO的其他答案中找不到解决方案。因此，我们将不胜感激。
不会有完美的正方形（除非我们考虑 i 从 -infinity 到 0 的数字。所以你 could/should 在负开始数上抛出 IllegalArgumentException，或者只是将开始设置为 0 .
让我们假设 A, B ≥ 0。
则A≤n²≤B等价于√A≤n≤√B，ceil(√A)≤n≤floor(√B)。
因此解数为floor(√B) - ceil(√A) + 1.
如果A < 0，将A替换为0。那么如果B < A，则无解。
@Bathsheba 更新：
最后，如果您不希望 0 被认为是一个完美的正方形，请将 "If A < 0, replace A by 0" 替换为 "If A < 1, replace A by 1."
我想求出两个数 A、B 的完全平方（数字可以是 positive/negative）。我也想实现 O(sqrt(abs(B))).
的时间复杂度我为此编写了以下代码：
count = (int)(Math.floor(Math.sqrt(Math.abs(B)) - Math.ceil(Math.sqrt(Math.abs(A))) + 1);
这通常运行良好，但当范围在 -ve 和 +ve 数字之间时失败。
例如范围是A = -1, B = 1。那么我认为它应该是return 2 (0, 1) 但是returns 1.
我在SO的其他答案中找不到解决方案。因此，我们将不胜感激。
不会有完美的正方形（除非我们考虑 i 从 -infinity 到 0 的数字。所以你 could/should 在负开始数上抛出 IllegalArgumentException，或者只是将开始设置为 0 .
让我们假设 A, B ≥ 0。
则A≤n²≤B等价于√A≤n≤√B，ceil(√A)≤n≤floor(√B)。
因此解数为floor(√B) - ceil(√A) + 1.
如果A < 0，将A替换为0。那么如果B < A，则无解。
@Bathsheba 更新：
最后，如果您不希望 0 被认为是一个完美的正方形，请将 "If A < 0, replace A by 0" 替换为 "If A < 1, replace A by 1."