OJ：约数个数

题目来源：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：利用约数个数定理：

OJ：约数个数

原文：http://blog.csdn.net/xzz_hust/article/details/18795407