如何在给定范围内找到完全平方数的数量？

Question

如何在给定范围内找到完全平方数的数量？

3

当t输入较大时，会因超时而报错。在给定范围内查找完全平方数的数量。

 #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>

    int main() 
    {

        double s,e,i;
       int t;
       scanf("%d",&t);
       for (;t>0;t--)
            {
             int cnt=0;
             scanf("%lf%lf",&s,&e);
             for (i=s;i<=e;i++)
                {
                 if (sqrt(i)==ceil(sqrt(i)))
                 cnt++;
                }
            printf("%d\n",cnt);
            }
        return 0;
    }

- Kumar Gaurav

2个回答

4

方法2（高效）：我们可以简单地对a和b分别取平方根，然后使用以下公式计算它们之间的完全平方数数量：

floor(sqrt(b)) - ceil(sqrt(a)) + 1

我们对sqrt(b)向下取整，是因为我们需要考虑b之前的数字

我们对sqrt(a)向上取整，是因为我们需要考虑a之后的数字

例如，令b = 24，a = 8。floor(sqrt(b)) = 4，ceil(sqrt(a)) = 3，平方数的数量为4-3+1 = 2。这两个数是9和16。

- Dharmesh poladiya

比起原始答案，这个解释更好，并且代码更简洁。 - Vinay Kumar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- haccks · Accepted Answer

有一个技巧。

找到下限和上限的平方根
取它们的整数部分，然后
从上限的整数部分减去下限的整数部分。

您还需要检查下限是否为完全平方数。如果是，则将差加上1。

例如：在1和100之间的完全平方数数量为10-1 = 9。由于1也是完全平方数，因此再加上1，结果将为10。

int result = (int)sqrt(upper_bound) - (int)sqrt(lower_bound);  
if(lower_bound == (int)sqrt(lower_bound)*(int)sqrt(lower_bound))  
    result += 1;

请注意，我考虑了上下限的包含。