一个整数范围是否至少包含一个完全平方?

据我所知,计算一个数是否是平方并不比在困难的情况下计算它的平方根快。真正的情况是,你可以做一个预计算,知道它不是一个正方形,这可能会节省你的平均时间。

同样,对于这个问题,您可以进行预计算以确定sqrt(b)-sqrt(a)>=1,这意味着a和b相距足够远,它们之间一定有一个正方形。对于某些代数,这个不等式等价于(b-a-1)^2>=4*a,或者如果你想让它更对称,那么(a-b)^2+1>=2*(a+b)。所以这个预计算不需要平方根,只需要一个整数积和一些加法和减法。

如果a和b几乎完全相同,那么您仍然可以使用查看低阶二进制数字作为预计算的技巧来知道它们之间没有平方。但它们必须靠得很近,这样的预先计算可能不值得。

如果这些预计算是没有结论的,那么除了其他人的解决方案之外,我想不出其他任何方法,a<=天花板(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。

否则,将数字四舍五入并平方。如果这小于b,那么它是真的。

为了避免a等于b的问题,您应该首先检查它。因为这个案子总是假的。

如果你接受计算两个平方根,由于它的单调性,你得到了这个不等式,它相当于你的开始一个:

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

因此,如果 floor(sqrt(a)) != floor(sqrt(b)) , floor(sqrt(b)) - 1 一定是这样的 n .

1. 得到较低数字的平方根,并将其四舍五入

求sqrt(a)和sqrt(b)的积分部分,比如sa和sb。

如果sa ² =a,则输出是。

² =b和sa=sb-1,则输出no。

Else输出编号。

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

通过使用类似于二进制搜索的方法,可以完全避免计算平方根。

从n的猜测开始,n=1,然后计算n

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

如果n<<b、 你猜对了。 如果<b<n、 你让它接近当前+先前猜测的平均值。

除了JDunkerley的不错的解决方案(+1),还有一个可能的改进需要测试和使用 integer square roots

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

一种方法是用牛顿法来寻找 integer square root 对于 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;
}