题解 | 阶乘分解

挺水的一题...了解阶乘的定义就可以做了。
因为阶乘是连着乘下去的，所以对于一个，它的出现次数就是，对于，的出现次数是，不过有一半的数在处被算过了那个不能乘上去。将枚举到即可。效率是的
注意开long long

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int p[N], vis[N], cnt, n;

int main() {
    scanf("%d", &n);
    for(int i = 2; i <= n; ++i) {
        if(!vis[i]) p[++cnt] = i;
        for(int j = 1; j <= cnt && i * p[j] <= n; ++j) {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) break;
        }
    }
    for(int i = 1; i <= cnt; ++i) {
        long long tot = 0;
        for(long long j = p[i]; j <= n; j *= 1LL * p[i]) tot += 1LL * n / j;
        printf("%d %lld\n", p[i], tot);
    }
}