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;
}