求因子个数-时间开销优化版本

Time Limit: 1000 ms
Memory Limit: 32768 mb

题目描述

输入n个整数,依次输出每个数的约数的个数

输入输出格式

输入描述:

输入的第一行为N，即数组的个数(N<=1000)
接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)
当N=0时输入结束。

输出描述:

可能有多组输入数据，对于每组输入数据，
输出N行，其中每一行对应上面的一个数的约数的个数。

输入输出样例

输入样例#:

5
1 3 4 6 12

输出样例#:

1
2
3
4
6

题目来源

清华大学上机题

坑点

有时间限制，而num最大为1000000000，若使用最直接的做法，会有部分数据测试时运行超时

比如下面的代码就出现这一情况

#include <stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;++i)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;++i)
    {
        int cnt=0;
        for(int j=1;j<=a[i];++j)
        {
            if(a[i]%j==0)
            cnt++;
        }
        printf("%d\n",cnt);
    }
}

AC

#include <math.h>
#include <stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;++i)
        scanf("%d",&a[i]);
    for(int i=0;i<n;++i)
    {
        int cnt=0;
        for(int j=1;j<=sqrt(a[i]);++j)
        {
            if(j*j==a[i])//比如3*3=9
            {
                cnt+=1;
            }
            else if(a[i]%j==0)
            {
                cnt+=2;//因子有一必有二，而我们只做到根号num，因此加2
            }
        }
        printf("%d\n",cnt);
    }
}