题目1087：约数的个数
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：9871
解决：3285
-
题目描述：
-
输入n个整数,依次输出每个数的约数的个数
-
输入：
-
输入的第一行为N，即数组的个数(N<=1000)
接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)
当N=0时输入结束。
-
输出：
-
可能有多组输入数据，对于每组输入数据，
输出N行，其中每一行对应上面的一个数的约数的个数。
-
样例输入：
-
5 1 3 4 6 12
-
样例输出：
-
1 2 3 4 6
-
来源：
- 2011年清华大学计算机研究生机试真题
-
- 约数个数定理。
- 之前的练习已经求出了某数的质因数的个数，分别为a,b,c,d……。根据约数个数定理，约数个数可由每个质因数的个数加一的乘积求得。即（a+1）*(b+1)*（c+1）*(d+1)........
-
-
#include <cstdio> #include <cstring> bool num[100001]; int prime[100001]; int primesize; void init(){primesize=0;for(int i=0;i<100001;i++){num[i]=false;}for(int i=2;i<100001;i++){if(num[i]==true)continue;prime[primesize++]=i;for(int j=i+i;j<100001;j+=i){num[j]=true;}} } int main(){init();int n,a[1005];while(scanf("%d",&n)!=EOF&&n!=0){memset(a,0,sizeof(a));for(int i=0;i<n;i++){scanf("%d",&a[i]);}for(int i=0;i<n;i++){int ansPrime[30];//保存质因数int ansSize=0;//保存质因数的个数，不要忘了将其初始化为零int ansNum[30];//保存质因数的次数for(int j=0;j<primesize;j++){if(a[i]%prime[j]==0){ansPrime[ansSize]=prime[j];ansNum[ansSize]=0;while(a[i]%prime[j]==0){ansNum[ansSize]++;a[i]=a[i]/prime[j];}ansSize++;}if(a[i]==1)break;}if(a[i]!=1){ansPrime[ansSize]=a[i];ansNum[ansSize]=1;ansSize++;}int ans=1;for(int k=0;k<ansSize;k++){ans=ans*(ansNum[k]+1);}printf("%d\n",ans);}}return 0; }