1948 Problem D 约数的个数

问题 D: 约数的个数

时间限制: 1 Sec  内存限制: 32 MB

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

输入

输入的第一行为N，即数组的个数(N<=1000)

接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)

当N=0时输入结束。

输出

可能有多组输入数据，对于每组输入数据，

输出N行，其中每一行对应上面的一个数的约数的个数。

样例输入

6
1 4 6 8 10 12
0      

样例输出

1
3
4
4
4
6      

经验总结

AC代码

#include <cstdio>
#include <cmath>
const int maxn=1000001;
int p[maxn]={0},prime[maxn],num=0;
void Find_Prime()
{
  for(int i=2;i<maxn;i++)
  {
    if(p[i]==false)
    {
      prime[num++]=i;
      for(int j=i+i;j<maxn;j+=i)
        p[j]=true;
    }
  }
}
struct factor
{
  int cnt,x;
}fac[10];
int main()
{
  int n,m;
  Find_Prime();
  while(~scanf("%d",&m))
  {
    if(m==0)  break;
    for(int j=0;j<m;j++)
    {
      scanf("%d",&n);
      int no=0,sqr=(int)sqrt(1.0*n);
      for(int i=0;i<num&&prime[i]<=sqr;i++)
      {
        if(n%prime[i]==0)
        {
          fac[no].cnt=0;
          fac[no].x=prime[i];
          while(n%prime[i]==0)
          {
            fac[no].cnt++;
            n/=prime[i];
          }
          no++;
        }
        if(n==1)  break;
      }
      if(n!=1)
      {
        fac[no].x=n;
        fac[no++].cnt=1;
      }
      int count=1;
      for(int i=0;i<no;i++)
        count*=(fac[i].cnt+1);
      printf("%d\n",count);
    }  
  }
  return 0;
}