九度OJ-1087：约数的个数

　　这题的难点依然是在大数据的处理上，只要不存储具体的因数及其幂次，而直接累乘到pro上即可。不赘述。

题目地址：点击打开链接 题目描述：

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

输入：

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

输出：

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

样例输入： 5 1 3 4 6 12 样例输出： 1 2 3 4 6 来源： 2011年清华大学计算机研究生机试真题 答疑： 解题遇到问题?分享解题心得?讨论本题请访问： http://t.jobdu.com/thread-7810-1-1.html #include <iostream> #include <cmath> using namespace std; int main(){ int n,N,pro; bool isPrime[35000]; int prime[4000]; int primeSize; int power; //preprocess for (int i=2;i<35000;i++){ isPrime[i]=true; } primeSize=0; for (int i=2;i<35000;i++){ if (isPrime[i]==true){ prime[primeSize]=i; primeSize++; for (int j=2*i;j<35000;j+=i){ isPrime[j]=false; } } } while(cin>>N,N){ for (int index=0;index<N;index++){ //initiate cin>>n; pro=1; //resolve for (int i=0;i<primeSize;i++){//resolve n if (n%prime[i]==0){ power=0;//initiate power do{ power++; n/=prime[i]; } while(n%prime[i]==0); pro*=power+1; } else if ( prime[i]>(int)(sqrt(n)+1) ){//则n已经是一个素数 pro*=2; break; } if (n==1) break; } //output cout<<pro<<endl; } } return true; }