找到两个数字之间的完美平方数的最快方法是什么？ [英] What is the fastest way to find the number of perfect squares between two numbers?

问题描述

我用过：



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))

这篇关于找到两个数字之间的完美平方数的最快方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！