形式化题目

给定整数 $n$，把 $n! = 1 \cdot 2 \cdots n$ 写成算术基本定理的形式

要求按 $p_i$ 从小到大的顺序，输出每一对 $(p_i, c_i)$。

例如 $n = 5$ 时 $5! = 120 = 2^3 \cdot 3^1 \cdot 5^1$，所以输出三行：

1
2
32 3
3 1
5 1

注意 $n!$ 的质因数集合恰好是「所有不超过 $n$ 的质数」，记 $\pi(n)$ 为不超过 $n$ 的质数个数， 输出的行数就是它——$n = 10^6$ 时 $\pi(10^6) = 78498$ 行。

正解

思路

先想最直接的做法。 按题意算出 $n!$ 的数值，再从小到大拿质数去试除。题面给的上界是 $n \leqslant 10^6$，这个做法在本题规模下根本跑不动：$10^6!$ 的十进制位数约 $5.5 \times 10^6$ 位， 光是做 $n$ 次大整数乘法就已经超时，之后还要用 $\pi(n) \approx 7.8 \times 10^4$ 个质数逐个去试除这个巨数。

退一步，还可以对每个 $i = 2, 3, \dots, n$ 单独试除分解，把得到的指数累加起来。 这个做法不用大整数，但每个 $i$ 试除一遍要 $O(\sqrt i)$，总计

仍然远远超出 1s。

瓶颈在哪里？ 两个朴素做法都默认「必须逐个处理 $i$」。但我们要的只是每个质数在整个 乘积里出现了几次，这件事本身可以按质数分开统计：质数 $p$ 的指数只和 $p$、$n$ 有关， 和其他质数互不影响。于是问题从「分解 $n$ 个数」变成「对每个质数单独数一遍」，而单独的 一遍有闭式公式。

关键观察：勒让德公式。 在 $1, 2, \dots, n$ 里数 $p$ 的个数可以分层：

• 能被 $p$ 整除的数有 $\lfloor n/p \rfloor$ 个，每个至少贡献 1 个因子 $p$；
• 能被 $p^2$ 整除的数有 $\lfloor n/p^2 \rfloor$ 个，每个还要再贡献 1 个；
• 能被 $p^3$ 整除的数有 $\lfloor n/p^3 \rfloor$ 个，每个再贡献 1 个；
• …… 直到 $p^k > n$ 为止。

把这些层加起来，就是 $n!$ 中 $p$ 的总指数：

这个公式好记的直觉是「每 $p$ 个连续整数贡献 1 个 $p$，每 $p^2$ 个再补 1 个，每 $p^3$ 个再补 1 个」。 下面用 $n = 10$、$p = 2$ 验证一遍（$10! = 3628800 = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7$，所以 $c_2$ 应该是 8）。 表格的行为「哪个数」，列为「哪一层」，$\checkmark$ 表示这个数在第 $k$ 层被数到一次：

读表方式：横着看某个 $i$，它被打勾的次数正好是 $v_2(i)$；竖着看某一层，打勾的个数正好是 $\lfloor n/p^k \rfloor$。所以「按行求和」和「按列求和」得到同一个数，而按列求和只需要 $O(\log_p n)$ 次除法——不用去看任何单个 $i$。$k = 4$ 时 $\lfloor 10/16 \rfloor = 0$，循环到此停止。

剩下的问题：质数从哪来。 如果对每个 $p = 2, 3, \dots, n$ 都试除判断一次质数，就退化回 $O(n\sqrt n)$ 了。改用埃氏筛：先假设 $2 \sim n$ 全是质数，然后从小到大遇到质数 $i$ 就把 $i^2, i^2+i, i^2+2i, \dots$ 全部划掉。每个合数只会被划掉若干次（总次数 $O(n \log\log n)$）， 一次筛出全部质数。

于是完整流程只有三步：

1. 埃氏筛求出 $2 \sim n$ 的全部质数；
2. 对每个质数 $p$ 用勒让德公式求 $c_p$；
3. 按 $p$ 升序输出 p c。

输出形式的两个细节。 第一，$c_p$ 一定 $\geqslant \lfloor n/p \rfloor \geqslant 1$（因为 $p \leqslant n$）， 所以每个筛出来的质数都恰好占一行，不需要额外判断。第二，$n = 1$ 时 $1! = 1$ 没有质因子， 输出为空——这一点在只看 p c 两列的输出题面里最容易被忽略，本题也要照顾到。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 16:13
# update_at: 2026-10-01 16:19

import sys
from math import isqrt


def sieve(n: int) -> bytearray:
    """埃氏筛：返回长度 n+1 的表，is_prime[i] 非 0 表示 i 是质数。"""
    is_prime = bytearray([1]) * (n + 1)          # 先全部当质数，再划掉合数
    is_prime[:2] = bytes(min(2, n + 1))          # 0 和 1 不是质数
    for i in range(2, isqrt(n) + 1):
        if is_prime[i]:
            # 从 i*i 起把 i 的倍数清成 0：切片赋值一次清空整段，长度用 range 数出来
            is_prime[i * i :: i] = bytes(len(range(i * i, n + 1, i)))
    return is_prime


def legendre(p: int, n: int) -> int:
    """勒让德公式：n! 中质数 p 的指数 = n//p + n//p^2 + n//p^3 + ..."""
    power, count = n, 0
    while power:
        power //= p
        count += power
    return count


def solve() -> None:
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it, 0))

    # n! 的质因数只可能是 <= n 的质数，筛出它们再逐个套勒让德公式
    is_prime = sieve(n)
    out = [f"{p} {legendre(p, n)}" for p in range(2, n + 1) if is_prime[p]]
    # 每个质数至少贡献一个因子，必有 c >= 1，所以非空时直接 join 就是题面要求的分行输出
    sys.stdout.write("\n".join(out) + "\n" if out else "")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 18:10
 * update_at: 2026-10-06 18:10
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

typedef long long ll;

int n;
bool is_prime[MAXN]; // is_prime[i] = true 表示 i 是质数

// 埃氏筛：筛出 2 ~ n 的全部质数
void sieve(int limit) {
    for (int i = 2; i <= limit; i++) {
        is_prime[i] = true;
    }
    for (int i = 2; (ll)i * i <= limit; i++) {
        if (is_prime[i]) {
            // 从 i*i 开始把 i 的倍数划掉
            for (int j = i * i; j <= limit; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

// 勒让德公式：计算 n! 中质数 p 的指数
// c_p = n/p + n/p^2 + n/p^3 + ...
ll legendre(int p, int nn) {
    ll power = nn;
    ll cnt = 0;
    while (power) {
        power /= p;
        cnt += power;
    }
    return cnt;
}

void solve() {
    cin >> n;

    // n = 1 时 1! = 1，没有质因子，输出为空
    if (n < 2) {
        return;
    }

    sieve(n);

    for (int p = 2; p <= n; p++) {
        if (is_prime[p]) {
            cout << p << " " << legendre(p, n) << "\n";
        }
    }
}

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

    solve();

    return 0;
}

复杂度

设筛上界为 $N$（本题 $N = n$）。

• 时间：埃氏筛 $O(N \log\log N)$；扫一遍 $2 \sim N$ 挑质数 $O(N)$；勒让德公式对质数 $p$ 只做 $\lfloor \log_p N \rfloor$ 次整除，把次数按「第 $k$ 层有哪些质数」重新分组可得 $\sum_{p \leqslant N} \lfloor \log_p N \rfloor = \sum_{k \geqslant 1} \pi\!\left(\lfloor N^{1/k} \rfloor\right)$， 即 $\pi(N) + \pi(\sqrt N) + \cdots = 78498 + 168 + 25 + 11 + \cdots = 78734$ 次， 比 $\pi(N)$ 只多一个 $O(\sqrt N)$ 级别的尾巴。总计 $O(N \log\log N)$。
• 空间：筛表是 $N + 1$ 字节的 bytearray（$10^6$ 时 1MB）；输出共 $\pi(N) \leqslant 78498$ 行、 约 706KB 文本。总计 $O(N)$，实测峰值 22.7MB（含解释器），远低于 128MB。

实测：$n = 10^6$ 用时 0.05s；真实数据 5 组（$9, 100, 9753, 99991, 10^6$）全部通过， 单组最长 0.050s。

对比：大整数做法要先算 $10^6!$（约 550 万位十进制）再试除；逐个试除分解是 $O(n\sqrt n) \approx 10^9$。 把「逐个 $i$ 分解」换成「逐个质数按层计数」，正是本题的关键一步。

实现上唯一需要留意的是埃氏筛的划除方式。纯 Python 里写 for j in range(i*i, n+1, i): is_prime[j] = 0 会执行约 $N \log\log N \approx 2.1 \times 10^6$ 次 Python 级赋值，反而成为瓶颈； 代码改用切片批量赋值 is_prime[i*i::i] = bytes(len(range(i*i, n+1, i)))，把整段连续内存一次清空， 划除工作落到 C 层完成，这才是 0.05s 的来源。另外 range(i*i, n+1, i) 在 $i^2 > n$ 时长度为 0， bytes(0) 赋值不会报错，所以不必额外加 if。

总结

本题的骨架是「不分解乘积，而是逐个质数统计」：

• $n!$ 的质因数集合就是所有 $\leqslant n$ 的质数，用埃氏筛一次求出；
• 每个质数的指数彼此独立，可以单独用勒让德公式 $c_p = \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \cdots$ 算出；
• 公式的直觉是分层数：每 $p$ 个连续整数贡献 1 个 $p$，每 $p^2$ 个再补 1 个；
• 整体复杂度 $O(n \log\log n)$，把朴素的 $O(n\sqrt n)$ 和大整数做法都甩开。

这类「积的因子统计」问题，通用的思路都是交换求和顺序：不要把因子按「哪个数」分组， 而要按「哪个质数」分组，分组后往往一个闭式公式就能解决。

图示解析

整条思路可以压成下面这张路线图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17求解目标：n! = ∏ p^c  的每个 (p, c)
   │
   ├─ 想法 A：算出 n! 再试除 ────► 死因：10^6! 有 ~5.5×10^6 位十进制，乘法都超时
   ├─ 想法 B：对 i = 2..n 逐个试除 ──► 死因：Σ√i = O(n√n) ≈ 10^9
   │
   ▼
关键观察：指数可分离 —— c_p 只依赖 p 和 n，与其他质数无关
   │
   ├─ 有哪些 p ──► 埃氏筛，O(n log log n) 一次求出全部 ≤ n 的质数
   │
   └─ c_p 怎么算 ──► 勒让德公式分层数：
                     k=1 : ⌊n/p⌋    个「至少含一个 p」
                     k=2 : ⌊n/p²⌋   个「至少含两个 p」，再补 1
                     k=3 : ⌊n/p³⌋   … 直到 p^k > n
   │
   ▼
对每个质数 p 输出一行 "p c_p"（c_p ≥ 1 恒成立）

图中最关键的一步是中间那个分岔：朴素做法都在「枚举 $i$」这一侧， 而正解把它拆成「枚举 $p$」——左支负责回答有哪些 $p$（交给筛法）， 右支负责回答每个 $p$ 出现几次（交给公式）。两支的规模分别是 $O(n\log\log n)$ 与 $O(\log_p n)$，都比原来的 $O(\sqrt i)$ 试除便宜得多。