基础数学算法-阶乘分解

题目-阶乘分解

问题分析

对于质数$p$, 计算$1\times 2\times 3\times \mathrm{4...}\times n$中$p$出现的次数
$ans=\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+...+\frac{n}{p^k}$, 同时$n$是迭代的, 也就是说n /= p

算法步骤

输入$n$, 计算$[1,n]$之间出现的质数, 然后分别使用上述的公式计算$p$出现的次数
输出即可, 算法时间复杂度瓶颈在处理质数, $O(n)$

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

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

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    init(n);

    for (int i = 0; i < cnt; ++i) {
   
        int p = primes[i];
        int cnt = 0;
        for (int j = n; j; j /= p) cnt += j / p;
        if (cnt == 0) continue;
        cout << p << ' ' << cnt << '\n';
    }

    return 0;
}