<算法进阶指南>题解补全计划—进阶指北

此篇属于算法进阶指南题解补全计划—进阶指北收录题解:传送门

阶乘分解（附质数板子证明）

思路指北

质数筛板子证明

code

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e6 + 10;

int primes[N];
int cnt;
bool st[N];
int n;


void init(int n)
{
    for(int i = 2;i <= n;i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0;j < cnt && i * primes[j] <= n;j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main()
{
    cin >> n;
    init(n);
    for(int i = 0;i < cnt;i ++)
    {
        int p = primes[i];
        int  s = 0;
        for(int j = n;j;j/=p)
           s += j/p;
    cout << p << ' ' << s << endl;
    }
    return 0;
}