7-6【拓展编程_课后练习】（递归）【陈越实验案例2-7】 素因子分解 (20分)

7-6【拓展编程_课后练习】（递归）【陈越实验案例2-7】 素因子分解 (20分)

#include<stdio.h>
#define max 1000000//这里素数表要足够大！！
int a[max] = { 0 }, b[max], c[max] = { 0 };
int flag1 = 0, sum;
int creatsushu()//构建素数表,存放在b[];
{
	int i, j;
	for (i = 2; i <= max/2; i++) {
		if (a[i] == 0) {
			for (j = 2; i * j <=max; j++)
				a[i * j] = 1;
		}
	}
	for (i = 2,j=0; i < max; i++) {
		if (a[i] == 0)b[j++] = i;
	}
	return j;
}
void f(int j, int n)
{
	int i;
	if (n == 1) {
		flag1 = 1;
		int flag = 1;
		printf("%d=", sum);
		for (i = 0; i < j; i++) {
			if (c[i]) {
				if (flag) {
					if (c[i] != 1)
						printf("%d^%d", b[i], c[i]);
					else printf("%d", b[i]); 
					flag = 0;
				}
				else {
					if (c[i] != 1)
						printf("*%d^%d", b[i], c[i]);
					else printf("*%d", b[i]);
				}
			}
		}
	}
	else {
		for (i = 0; i < j; i++) {
			if (n % b[i] == 0) {
				c[i]++;
				f(j, n / b[i]);
				if (flag1)break;
			}
		}
	}
}
int main()
{
	int n, j;
	scanf("%d", &n);
	sum = n;
	j = creatsushu();
	if (n == 1)printf("1=1");
	else f(j, n);
	return 0;
}