C语言时间超限问题  代码如下


#include<stdio.h>
#include<math.h>
int main()
{
    int n, sum;
    float a;
    while (scanf_s("%d", &n) != EOF)
    {
        sum = 0;
        for (size_t i = 1; i <= n; i++)
        {
            a = sqrt(i);
            if (a == (int)a) sum = sum + 1;
        }
        printf("%d\n", sum);

    }
}



在oj上提交，时间超限。

你都不肯将题目告知大家，那大家能猜出你想完成什么功能？

从你的代码来看，你就是想输出 n的平方根的整数部分，那为什么不直接 printf( "%.0f\n", floor(sqrt(n)) );

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

int main( void )
{
    for( unsigned n; scanf("%u",&n)==1; )
        printf( "%.0f\n", floor(sqrt(n)) );
}

忘记了。
题目：

输出[1，n]内所有的完全平方数。

输入
输入一个正整数n，n < 2^30

输出
输出[1，n]内所有的完全平方数。

样例输入
10
100
样例输出
3
10

是输出完全平方数个数。

取值范围最大 2的30次方
你每一个数字都尝试一次 O(n)太慢 导致超时
你可以换一个思路
一个数字对应一个完全平方数
比如 5 对应 25
只要一个数字的平方没有超过n
那么一定有一个完全平方数在里面
反过来想就是 n开根 取整 是最后一个完全平方数的对应数
包括n开方取整在内前面全部数字都有对应完全平方数
那就很简单了
(int)sqrt(n)+1
就可以了
+1是处理 0
比如 [0,5]有多少个完全平方数
5开根取整是 2
表示包括2在内 前面的数字都有完全平方数
0 1 2 一共是3 这3个数字对应完全平方数是 0 1 4
符合题目要求的 范围0-5
数量是3

开最大值平方取整，就是完全平方数的值

说实话，这个题目看不懂，要求输出所有的完全平方数，然而，样例输入和样例输出又是那个样子。
这里有三个技巧：1、最大数一半的平方是绝对要大于最大数的！所以，循环到最大数一半即可，这样可以节省不少的时间；2、两个数相乘所需要的时间也必定小于开平方所需要的时间。3、当 j 大于 i 的平方，中断此次循环，进一步节省时间。下面是我的程序：

#include<stdio.h>
int main()
{
    int i,j,n,sum = 0;
    scanf_s("%d", &n);

    for (i = 1; i <= n / 2; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (j == i * i)
            {
                printf("%d\n", j);
                sum += 1;
            }
            else if(j > i * i)      // 当 j 大于 i 的平方，中断此次循环，进一步节省时间
                break;
        }

    }
    printf("%d\n", sum);
}

懂了，谢谢大哥。

谢谢大哥。