阶乘分解

给定整数 N ，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。

输入格式

一个整数N。

输出格式

N! 分解质因数后的结果，共若干行，每行一对pi,ci，表示含有pcii项。按照pi从小到大的顺序输出。

数据范围

1≤N≤1000000
输入样例：

5

输出样例：

2 3
3 1
5 1

样例解释

5!=120=2^3∗3∗5

思路

考虑从质数的幂出发，比如一个质数$p^{k}$,我们可以先加上含$p^{1}$的合数，也就是$p^{1}$的倍数的个数，然后再加上$p^{2}$的倍数的个数，。。。。最后加上$p^{k}$的倍数的个数

#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;

ll N;
int P[maxn],tail;
bool vis[maxn];
void init(){
    for(ll i = 2;i<maxn;i++){
        if(!vis[i]){
            P[tail++] = i;
            for(ll j = i*i;j<maxn;j+=i){
                vis[j] = true;
            }
        }
    }
}
void fun(){
    for(int i = 0;i<tail;i++){
        int cnt = 0;
        for(ll j = P[i];j<=N;j*=P[i]){
            cnt += N/j;
        }
        if(cnt) printf("%d %d\n",P[i],cnt);
    }
}
int main(){
    init();
    cin>>N;
    fun();
    return 0;
}