题目来源:http://ac.jobdu.com/problem.php?pid=1087
方法1:类似于判断质数,只需要枚举 sqrt(n) 个数就可以得到n的约数个数了,效率很高,10亿没问题。
#include <stdio.h> #include <string.h> #include <cmath> int num[1005]; int main() { int N; while (scanf("%d", &N) != EOF) { for (int i = 0; i < N; i++) { scanf("%d", &num[i]); } for (int i = 0; i < N; i++) { int res = 2; int sq = floor( sqrt(num[i] * 1.0) + 0.5 ) ; // 0.5 为修正浮点数误差 for (int j = 2; j <= sq; j++) { if (num[i] % j == 0) { // 能整除则加2,因为有前后两个约数 res += 2; } } if (sq * sq == num[i]) { --res; } printf("%d\n", res); } } return 0; }
方法2:利用约数个数定理:
对于一个大于1正整数n可以分解质因数:n=p1^a1*p2^a2*p3^a3*…*pk^ak,
则n的正约数的个数就是(a1+1)(a2+1)(a3+1)…(ak+1) .
其中p1,p2,p3,…pk都是n的质因数;a1、a2、a3…ak是p1、p2、p3,…pk的指数。
这种方法看似简单,但要分解质因数,实现起来有点麻烦。用第一种方法其实已经够了。