约数个数定理
对于一个大于1的正整数n可以分解质因数：n = p1^a1 * p2^a2 * p3^a3 * … * pn^an, 则n的正约数的个数为：（a1 + 1） * （a2 + 1） * … *（an + 1）。其中p1,p2,pn都是n的质因数，a1, a2…an是p1,p2,pn的指数
证明
n可以分解质因数：n=p1^a1 * p2^a2 * p3^a3 * … * pk^ak,
由约数定义可知p1^a1的约数有：p1^0, p1^1, p1^2……p1^a1 ,共（a1+1）个；同理p2^a2的约数有（a2+1）个……pk^ak的约数有（ak+1）个
故根据乘法原理：n的约数的个数就是（a1+1）*（a2+1）*（a3+1）*…* （ak+1）
题目
[html] view plaincopy
题目描述：
输入n个整数，依次输出每个数的约数的个数
输入：
输入的第一行为N,即数组的个数（N<=1000）
接下来的1行包括N个整数，其中每个数的范围为（1<=Num<=1000000000）
当N=0时输入结束。
输出：
可能有多组输入数据，对于每组输入数据，
输出N行，其中每一行对应上面的一个数的约数的个数。
样例输入：
5
1 3 4 6 12
样例输出：
1
2
3
4
6
代码
[cpp]
#include <stdio.h>
#include <stdlib.h>
#define N 40000
typedef long long int lint;
int prime[N], size;
void init（）
{
int i, j;
for （prime[0] = prime = 0, i = 2; i < N; i ++） {
prime[i] = 1;
}
size = 0;
for （i = 2; i < N; i ++） {
if （prime[i]） {
size ++;
for （j = 2 * i; j < N; j += i）
prime[j] = 0;
}
}
}
lint numPrime（int n）
{
int i, num, *ansnum, *ansprime;
lint count;
ansnum = （int *）malloc（sizeof（int） * （size + 1））；
ansprime = （int *）malloc（sizeof（int） * （size + 1））；
for （i = 2, num = 0; i < N && n != 1; i ++） {
if （prime[i] && n % i == 0） {
ansprime[num] = i;
ansnum[num] = 0;
while （n != 1 && n % i == 0） {
ansnum[num] += 1;
n /= i;
}
num ++;
}
}
if （n != 1） {
ansprime[num] = n;
ansnum[num] = 1;
num ++;
}
for （i = 0, count = 1; i < num; i ++） {
count *= （ansnum[i] + 1）；
}
free（ansnum）；
free（ansprime）；
return count;
}
int main（void）
{
int i, n, *arr;
lint count;
init（）；
while （scanf（"%d", &n） != EOF && n != 0） {
arr = （int *）malloc（sizeof（int） * n）；
for （i = 0; i < n; i ++） {
scanf（"%d", arr + i）；
}
for （i = 0; i < n; i ++） {
count = numPrime（arr[i]）；
printf（"%lld\n", count）；
}
free（arr）；
}
return 0;
}
/**************************************************************
Problem: 1087
User: wangzhengyi
Language: C
Result: Accepted
Time:190 ms
Memory:1068 kb
****************************************************************/