学步园

题目连接：http://zuojie.3322.org:88/soj/problem.action?id=2666

Description

给你一个数 n (1 < n <= 1000000) ,求 n! (n的阶乘)的质因数分解形式，质因数分解形式为

n=p1^m1*p2^m2*p3^m3……

*  这里 p1 < p2 < p3 < …… 为质数
*  如果 mi = 1, 则   ^ mi   就不需要输出 

Input

输入是多case的，每行一个数n，1 < n <= 1000000，当n等于0时输入结束

Output

每个n输出一行，为它的质因数分解形式

Sample Input

6
7
0

Sample Output

6=2^4*3^2*5
7=2^4*3^2*5*7

Author

windy7926778

题目是windy教主出的，意在考察对质因数分解和阶乘的深入理解。

如果按照普通思维，分别从1分解到n的话，超时的可能性非常大，而且内存开销也极其庞大。

必须转换思维。直接从n下手。

举个例子

n!里面包含了多少个2，假设n=10

那么个数是：10/2+10/4+10/8=5+2+1

于是快速方法就得到了

我们这样就可以直接统计每一个素因子出现了多少次，而1000000以内的素因子个数总共只有7w多，也就是说O(n)的速度是可行的！

我的代码：

#include<stdio.h>
#include<string.h>
#define MAXN 1000000
typedef long long LL;

bool flag[MAXN+1];
int prime[MAXN+1];
int ans[MAXN+1];
int MAX,num=0;

void init()
{
	LL i,j;
	for(i=2;i<=MAXN;i++)
	{
		if(!flag[i])
		{
			prime[num++]=(int)i;
			for(j=i*i;j<=MAXN;j=j+i)
				flag[j]=true;
		}
	}
}

void solve(int n)
{
	int i,N;
	for(i=0;prime[i]<=n&&i<num;i++)
	{
		N=n;
		while(N)
		{
			ans[i]=ans[i]+N/prime[i];
			N=N/prime[i];
		}
	}
	printf("%d=",n);
	if(ans[0]==1)
		printf("2");
	else if(ans[0]>1)
		printf("2^%d",ans[0]);
	for(i=1;prime[i]<=n&&i<num;i++)
	{
		if(ans[i]==1)
			printf("*%d",prime[i]);
		else if(ans[i]>1)
			printf("*%d^%d",prime[i],ans[i]);
	}
	printf("\n");
}

int main()
{
	int n;
	init();
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		memset(ans,0,sizeof(ans));
		solve(n);
	}
	return 0;
}