题目链接

• Intelligent Factorial Factorization
  • 这是一道素因数分解题。
  • 因为数据范围非常小，所以直接暴力分解即可。
  • 首先使用欧拉筛预处理出≤10000（sqrt(n!)的上界）的所有素数；
  • 计算答案每一组的答案：从2-n每个数用不大于它的素数进行分解，分解方法具体如下：
  • 若i%prime[j]=0，则i=i/prime[j]，且将prime[j]的个数加一，循环直到i%prime[j]≠0时结束。若prime[j+1]<i，将j加一，否则将i加一。

代码：

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10010;
bool not_prime[maxn];
int prime[maxn];
int top=0;
int main()
{
	int T;
	scanf("%d",&T);
	int a[T];
	int maxN=0;
	for(int i=0;i<T;i++)
	{
		scanf("%d",&a[i]);
	}
	not_prime[0]=not_prime[1]=true;
	for(int i=2;i*i<maxn;i++)
	{
		if(!not_prime[i])
		{
			prime[top++]=i;
		}
		for(int j=0;j<top&&i*prime[j]<maxn;j++)
		{
			not_prime[i*prime[j]]=true;
			if(i%prime[j]==0)
			{
				break;
			}
		}
	}
	for(int i=sqrt(maxn)-1;i<=maxn;i++)
	{
		if(!not_prime[i])
		{
			prime[top++]=i;
		}
	}
	int kcase=0;
	for(int i=0;i<T;i++)
	{
		int map[maxn];
		memset(map,0,sizeof(map));
		for(int x=2;x<=a[i];x++)
		{
			for(int j=0;prime[j]<=x;j++)
			{
				int b=x;
				if(b%prime[j]==0)
				{
					int cnt=0;
					while(b>=prime[j]&&b%prime[j]==0)
					{
						b/=prime[j];
						cnt++;
					}
					map[prime[j]]+=cnt;
				}
			}
		}
		printf("Case %d: %d =",++kcase,a[i]);
		bool start=true;
		for(int p=0;prime[p]<=a[i];p++)
		{
			if(map[prime[p]]!=0)
			{
				if(start==true)
				{
					start=false;
					printf(" %d (%d)",prime[p],map[prime[p]]);
				}
				else
				{
					printf(" *");
					printf(" %d (%d)",prime[p],map[prime[p]]);
				}
			}
		}
		printf("\n");
	}
	return 0;
}