一系列整数是否至少包含一个完全平方数？

Question

给定两个整数 a 和 b，是否有一种有效的方法来测试是否存在另一个整数 n 使得 a ≤  ;n2 < b?

我不需要知道n，只需要知道是否至少有一个这样的n存在，所以我希望避免计算任何的平方根区间内的数字。

虽然 测试单个整数是否是完美平方比计算平方根更快，范围可能很大，我也希望避免对范围内的每个数字执行此测试。

示例：

• intervalContainsSquare(2, 3) => false
• intervalContainsSquare(5, 9) =>; false（注意：9 在此区间之外）
• intervalContainsSquare(9, 9) => false（此区间为空）
• intervalContainsSquare(4, 9) =>; true（4 在此区间内）
• intervalContainsSquare(5, 16) => true（9 在此区间内）
• intervalContainsSquare(1, 10) => true（1、4、9 都在这个区间内）

Answer 1

据我所知，计算一个数字是否是平方并不比在困难情况下计算其平方根快。事实是，您可以进行预先计算来知道它不是正方形，这平均可以节省您的时间。

同样，对于这个问题，您可以进行预计算以确定 sqrt(b)-sqrt(a) >= 1，这意味着 a 和 b 相距足够远，它们之间必须有一个正方形。对于某些代数，这种不等式相当于 (ba-1)^2 >= 4*a 的条件，或者如果您想要更对称的形式，则 (ab)^2+1 >= 2* (a+b)。因此，这一预计算不需要平方根，只需一个整数乘积和一些加法和减法即可完成。

如果 a 和 b 几乎完全相同，那么您仍然可以使用查看低位二进制数字作为预计算的技巧来知道它们之间不存在正方形。但它们必须非常接近，以至于这种预先计算可能不值得。

如果这些预计算没有结论，那么除了其他人的解决方案之外，我想不出任何其他解决方案，a <= ceil(sqrt(a))^2 < b.

---

由于存在正确进行代数的问题：

sqrt(b)-sqrt(a) >= 1
sqrt(b) >= 1+sqrt(a)
b >= 1+2*sqrt(a)+a
b-a-1 >= 2*sqrt(a)
(b-a-1)^2 >= 4*a

---

另外：通常当 a 是一个很大的数时，您可以使用牛顿法或使用查找表后跟几个牛顿法步骤来计算 sqrt(a)。原则上计算 ceil(sqrt(a)) 比 sqrt(a) 更快，因为浮点算术可以简化为整数算术，并且因为您不需要那么多牛顿法步骤来确定高精度你就会扔掉。但实际上，如果数值库函数使用以微代码实现的平方根，则速度会快得多。如果出于某种原因您没有该微代码来帮助您，那么手动编写 ceil(sqrt(a)) 可能是值得的。也许最有趣的情况是 a 和 b 是无界整数（例如一千位数字）。但对于普通的、未过时的计算机上的普通大小的整数，你无法击败 FPU。

Answer 2

求较小数的平方根。如果这是一个整数那么你就完成了。
否则，将数字四舍五入并平方。如果小于 b 则为真。

这样您只需要计算一个平方根。

为了避免出现 a 等于 b 的问题，您应该先检查一下。因为这种情况总是假的。

Answer 3

如果您接受计算两个平方根，由于其单调性，您将得到这个不等式，它相当于您的起始不等式：

sqrt(a) <= n < sqrt(b)

因此，如果 floor(sqrt(a)) != Floor(sqrt(b)), floor(sqrt(b)) - 1 保证是这样的 n。

Answer 4

1. 取较小数的平方根并向上取整
2. 取较大数的平方根并向下取整
3. 如果 1 小于或等于 2，则会有一个完美的平方

Answer 5

求 sqrt(a) 和 sqrt(b) 的积分部分，即 sa 和 sb。

如果 sa² = a，则输出 yes。

如果 sb² = b 且 sa = sb-1，则输出 no。

如果sa＜ sb 输出是。

否则输出编号。

您可以优化上面的内容以摆脱 sqrt(b) 的计算（类似于 JDunkerly 的答案）。

或者您是否也想避免计算 a 和 b 的平方根？

---

使用类似于二分查找的方法可以完全避免计算平方根。

您首先猜测 n，n = 1 并计算 n²

考虑是否 a <= n < b、你可以停下来了。

如果 n <一个< b，你将你的猜测加倍。
如果 a < b＜ n，使其接近当前+先前猜测的平均值。

这将是 O(logb) 时间。

Answer 6

除了 JDunkerley 的不错的解决方案（+1）之外，可能还有一个可能的改进需要测试并使用 整数平方根 计算整数平方根

Answer 7

为什么你希望完全避免平方根？甚至在找到解决此问题的最有效方法之前，您就已经看到只需要 2 个平方根的方法。这是在 O(1) 时间内完成的，所以在我看来，你希望做出的任何改进都需要更多的时间来思考，而不是节省你的计算时间。我错了吗？

Answer 8

一种方法是使用牛顿法求 b整数平方根代码>.然后您可以检查该数字是否在该范围内。我怀疑它比简单地调用平方根函数更快，但它肯定更有趣：

int main( int argc, char* argv[] )
{
    int a, b;
    double xk=0, xk1;
    int root;
    int iter=0;
    a = atoi( argv[1] );
    b = atoi( argv[2] );

    xk1 = b / 32 + 1;  // +1 to ensure > 0
    xk1 = b;
    while( fabs( xk1 - xk ) >= .5 ) {
        xk = xk1;
        xk1 = ( xk + b / xk ) / 2.;
        printf( "%d) xk = %f\n", ++iter, xk1 );
    }

    root = (int)xk1;

    // If b is a perfect square, then this finds that root, so it also
    // needs to check if (n-1)^2 falls in the range.
    // And this does a lot more multiplications than it needs
    if ( root*root >= a && root*root < b ||
         (root-1)*(root-1) >= a && (root-1)*(root-1) < b )
        printf( "Contains perfect square\n" );
    else
        printf( "Does not contain perfect square\n" );

    return 1;
}