CH3101 阶乘分解

解法

暴力算每个数的质因子复杂度和为n×sqrt(n)。
先筛出1～n的质数，p的次数为n/(p^k),pk<=n.

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N=1e6+5;

int prime[N],v[N];
int n,num;

int read()
{
    int x=0,p=1; char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') p=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*p;
}

void Pri()
{
	for(int i=2;i<=n;i++)
	{
		if(!v[i]) prime[++num]=v[i]=i;
		for(int j=1;j<=num;j++)
		{
			if(prime[j]>v[i] || prime[j]*i>n) break ;
			v[prime[j]*i]=prime[j];
		}
	}
}

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);

	n=read();
	Pri();

	for(int i=1;i<=num;i++)
	{
		LL sum=prime[i],ans=0;
		while(sum<=n)
		{
			ans+=n/sum;
			sum*=prime[i];
		}
		printf("%ld %ld\n",prime[i],ans);
	}

    return 0;
}