一系列整数是否包含至少一个完美正方形？
给定两个整数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都在此间隔内） 就我所知，计算一个数是否是平方并不比计算平方根更快。 什么是真实的，你可以做一个预先计算，知道它不是一个正方形，这可能会平均节省你的时间。
同样，对于这个问题，你可以做一个预计算来确定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。
获取较低数字的平方根。 如果这是一个整数，那么你就完成了。 否则围起来并且把数字平方。 如果这小于b那么它是真的。
你只需要这样计算一个平方根。
为了避免出现a等于b的问题，您应该先检查一下。 因为这种情况总是错误的。
如果你接受计算两个平方根，由于它的单调性，你有这个不平等，这相当于你的开始一个不平等：
sqrt(a) <= n < sqrt(b)
因此，如果floor(sqrt(a)) != floor(sqrt(b)) ， floor(sqrt(b)) - 1保证是这样一个n 。
上一篇: Does a range of integers contain at least one perfect square?