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:利用约数个数定理:

对于一个大于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的指数。
这种方法看似简单,但要分解质因数,实现起来有点麻烦。用第一种方法其实已经够了。


OJ:约数个数

上一篇:反射机制


下一篇:C#编程总结(七)加密算法