题目1087：约数的个数

题目描述：

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

输入：

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

输出：

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

样例输入： 5 1 3 4 6 12 样例输出： 1 2 3 4 6

比较简单的方法是将给定的数据n开方得m，遍历m之前属于n的约数的个数num，若m为整数，则约数的个数为2*num-1，否则为2*num。

此方法可参考http://www.cnblogs.com/yinger/archive/2012/08/14/2639097.html

以下代码是利用素数的性质，是最开始时想到的方法，比较麻烦。

下面第一部分是自己摸索不断改正实现的，第二部分通过网上了解到约数个数定理学习实现的。

#include<stdio.h> #define MAX 100001 bool mark[MAX]; int primeSize = 0; int prime[MAX]; void init() { for (long long i = 2; i < MAX; i++) { if (mark[i]) continue; prime[primeSize++] = i; for (long long j = i * i; j < MAX; j += i) { mark[j] = true; } } } int ansNum[MAX]; int buf[1000]; /*int main() { init(); int n; while (scanf("%d", &n) != EOF) { if (n == 0) break; // for (int i = 0; i < n; i++) // scanf("%d", &buf[i]); for (int i = 0; i < n; i++) { scanf("%d", &buf[i]); int len = 0; for (int i = 0; i < primeSize; i++) ansNum[i] = 0; for (int j = 0; j < primeSize; j++) { if (buf[i] % prime[j] == 0) { while (buf[i] % prime[j] == 0) { ansNum[len]++; buf[i] /= prime[j]; } len++; } if (buf[i] == 1) break; } if (buf[i] > 1) ansNum[len++] = 1; int ans = 1; // printf("the len is %d\n", len); for (int m = 0; m < len; m++) ans += ansNum[m]; for (int m = 0; m < len; m++) { for (int n = m + 1; n < len; n++) ans += (ansNum[m] * ansNum[n]); } printf("%d\n", ans); } } return 0; }*/ //使用约数个数定理 int main() { init(); int n; while (scanf("%d", &n) != EOF) { if (n == 0) break; int x; for (int i = 0; i < n; i++) { scanf("%d", &x); int len = 0; for (int i = 0; i < primeSize; i++) ansNum[i] = 0; for (int j = 0; j < primeSize; j++) { if (x % prime[j] == 0) { while (x % prime[j] == 0) { ansNum[len]++; x /= prime[j]; } len++; } if (x == 1) break; } if (x > 1) ansNum[len++] = 1; int ans = 1; for (int m = 0; m < len; m++) ans = ans * (ansNum[m] + 1); printf("%d\n", ans); } } return 0; }

题目链接：

http://ac.jobdu.com/problem.php?pid=1087