一系列整数是否包含至少一个完美的正方形？

Question

鉴于两个整数a和b,有没有检验是否有另一个整数的有效方式n,使得？a ? n2 < b

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

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

例子:

• intervalContainsSquare(2, 3) =>假
• 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几乎完全相同,那么你仍然可以使用查看低阶二进制数字作为预计算的技巧来知道它们之间没有正方形.但它们必须如此紧密,以至于这种预先计算可能不值得.

如果这些预先计算是不确定的,那么我不能想到除了其他人的解决方案之外的任何其他解决方案,<= 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是一个很大的数字时,你可以用Newton的方法计算sqrt(a),或者用一个查找表和一些Newton的方法步骤来计算.原则上计算ceil(sqrt(a))比sqrt(a)更快,因为浮点运算可以简化为整数运算,并且因为你不需要那么多Newton的方法步骤来确定高精度你只是要扔掉.但实际上,如果使用微码中实现的平方根,数值库函数可以快得多.如果由于某种原因你没有那个微代码来帮助你,那么手动编码ceil(sqrt(a))可能是值得的.也许最有趣的情况是如果a和b是无界整数(比如,千位数).但对于普通的非过时计算机上的普通大小的整数,

Answer 2

获取较低数字的平方根.如果这是一个整数,那么你就完成了.否则将数字四舍五入.如果这小于b那么这是真的.

您只需要以这种方式计算一个平方根.

为了避免a等于b的问题,你应该先检查一下.因为这种情况总是错误的.