算法分析与设计 | 搜索（整数因子分解）

题目描述

???? 大于1的正整数 n 都可以分解为 n = x1 * x2 * ... * xm。例如：当n=12时，共有8种不同的分解式：
12 = 12
12 = 6*2
12 = 4*3
12 = 3*4
12 = 3*2*2
12 = 2*6
12 = 2*3*2
12 = 2*2*3
??? 对于给定正整数n，计算n共有多少种不同的分解式。

输入

?? 一行一个正整数n （1<=n<=1000000）

输出

?? n不同的分解式数目。

样例输入?

12
20
10

样例输出?

8
8
3

分析：

该题estimate（）方法是用来判断是否该数还有因子，search（）方法来进行记录因子，进行count++，最后在main函数中输出count要进行+1，是因为它本身的数字就是它的因子（比如6的整数因子，它自身6也是一种情况）。

代码：

//算法分析与设计：搜索（整数因子分解）
#include <stdio.h>
int count = 0;
int estimate(int n) {
	for (int i = 2; i < n; i++) {
		if (n % i == 0) return -1;
	}
	return 1;
}
void search(int m) {
	for (int i = 2; i < m; i++) {
		if (m % i == 0) {
			count++;
			if (estimate(m / i) == -1) {
				search(m / i);
			}
		}
	}
}
void main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		search(n);
		printf("%d\n", count + 1);
		count = 0;
	}
}