题目描述

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

样例

输入样例：
5
输出样例：
2 3
3 1
5 1
样例解释
5!=120=2^3∗3∗5

线性筛法

时间复杂度

$O(nlogn)$

参考文献

蓝书

C++ 代码

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
const int N=1000010;
bool st[N];
int prime[N],cnt;

void primes(int n)
{
    memset(st,false,sizeof st);
    cnt=0;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            prime[cnt++]=i;
        }
        for(int j=0;prime[j]*i<=n;j++)
        {
            st[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    int n,p;
    cin>>n;
    primes(n);
    for(int i=0;i<cnt;i++)
    {
        p=0;
        int t=n;
        while(t)p=p+t/prime[i],t/=prime[i];
         cout<<prime[i]<<" "<<p<<endl;
    }
    return 0;
}