解题思路

正常思路：
枚举1 ~ n，统计每个数的每个质因子的个数，但是时间复杂度为为O(n根号n)。
正确思路：
既然枚举数求质因子不行，那我们就枚举质因子求每个数含有此质因子的个数。

看似好像两个思路就是两层循环在内在外的关系，其实正确思路的时间复杂度为O(nlogn)

n！的每一个质因子都不会超过n，我们可以先筛选出1 ~ n的每个质数p，然后考虑阶乘n！中一共包含多少个质因子。
n!中质因子p的个数就等于1 ~ n每个数包含质因子p的个数之和。在1 ~ n中，p的倍数，即至少包含1个质因子p的显然有floor(n/p)个。而p^2的倍数，即至少包含2个质因子p的有floor(n/p^2)个。不过其中的1个质因子已经在floor(n/p)力统计过，所以只需要再统计第2个质因子，即累加上floor(n/p^2)，而不是2*floor(n/p^2)。
不理解可以看这个

AC代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N=1e6+100;

ll prime[N],t,num;
bool vis[N];
int n,cnt;

void Prime()
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt && i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

int main()
{
    cin>>n;
    Prime();
    for(int i=1;i<=cnt;i++)
    {
        num=0;t=prime[i];
        while(t<=n) num+=n/t,t*=prime[i];
        if(num!=0) cout<<prime[i]<<' '<<num<<endl;
    }
}