找到两个数字之间的完美平方数的最快方法是什么？

本文介绍了找到两个数字之间的完美平方数的最快方法是什么？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我用过： int（math.sqrt（last） - math.sqrt（first）） 用于获得答案，而不适用于某些测试用例。所以，任何人都可以建议我快速算法解决上述问题。

解决方案

我认为你需要sqrt（first）之后和之前的第一个整数之间的整数sqrt（last）。 要获得第一个整数，你可以使用 Math.Ceiling 。 要获得之前的第一个整数，您可以使用 Math.Floor 。 那么完整的公式应该是：

Math.Floor（Math.Sqrt（last）） - Math.Ceiling（Math.Sqrt（第一个））+ 1

+1因为如果之前的第一个整数last是第一个之后的第一个整数，差值为0但是你有1个整数。 例如：with sqrt（first）= 2.3 and sqrt（last） = 3.2 两个数字之间有1个整数= 3但是Floor（3.2）= 3和Ceiling（2.3）= 3 和Floor（3.2）-Ceiling（ 2.3）= 0. 这个c ode是使用C＃编写的，但我确信你可以找到其他语言的 floor 和 ceiling 函数。 / blockquote>

import math N = int（input（）） i 范围内（ 0 ，N）： first，last = map（int，input（）。split（ ）） print （math.floor（math.sqrt（last）） - math.ceil（math.sqrt（first））+ 1 ）

0到N之间的完美正方形数（包括两者），是N的整数平方根，让 isqrt（N）。 因此，第一个和第二个之间的完美平方数最后（包括边界），是差异 isqrt（最后） - isqrt（第一 - 1）。 整数广场重根可以计算为平方根转换为int，

int（math.sqrt（last）） - int（math.sqrt（first - 1 ））

I have used: int(math.sqrt(last) - math.sqrt(first)) for getting the answer, whereas it is not working for some test-cases. So, can anyone suggest me a fast algorithm for the above question.

解决方案

I think you need the number of integer between the first integer after sqrt(first) and before sqrt(last). To get the first integer after, you can use Math.Ceiling. To get the first integer before, you can use Math.Floor. Then the complete formula should be :

Math.Floor(Math.Sqrt(last)) - Math.Ceiling(Math.Sqrt(first)) + 1

+1 because if the first integer before last is the first integer after first, the difference will be 0 but you have 1 integer. For example : with sqrt(first) = 2.3 and sqrt(last) = 3.2 you have 1 integer between the two numbers = 3 but Floor(3.2)=3 and Ceiling(2.3)=3 and Floor(3.2)-Ceiling(2.3) = 0. This code is written using C#, but I'm sure you can found the floor and ceiling functions in other language.

import math N = int(input()) for i in range(0,N): first,last = map(int,input().split(" ")) print(math.floor(math.sqrt(last)) - math.ceil(math.sqrt(first)) + 1)

The number of perfect squares between 0 and N (both inclusive), is the integer square root of N, let isqrt(N). So the number of perfect squares between first and last (bounds inclusive), is the difference isqrt(last) - isqrt(first - 1). The integer square root can be computed as the square root cast to int,

int(math.sqrt(last)) - int(math.sqrt(first - 1))