最大真因数

GitHub跳转原题关系图返回列表

合数 n 的最大真因数是 n 除以它的最小质因子,于是求区间内合数按最小质因子分组后的商之和,用 min_25 筛在 O(n^{3/4}/log n) 内算出前缀和再作差。

OJ: roj

题目 ID: 1804

难度:提高+/省选-

标签:数学数论筛法Min_25 筛python

创建: 2026-10-08 04:13

更新: 2026-10-08 04:13

形式化题目

给定正整数 l≤rl \le r,对 [l,r][l, r] 中的每个合数取其最大真因数(不超过自身的最大因数), 求这些最大真因数之和。记 spf⁡(n)\operatorname{spf}(n) 为 nn 的最小质因子,答案为

S(l,r)  =  ∑l≤n≤rn 为合数nspf⁡(n). S(l, r) \;=\; \sum_{\substack{l \le n \le r \\ n \text{ 为合数}}} \frac{n}{\operatorname{spf}(n)} .

数据范围:1≤l≤r≤5×1091 \le l \le r \le 5 \times 10^9。

正解

思路

先化简单个合数。 若 nn 是合数,把它的因数从小到大排列。设 p=spf⁡(n)p = \operatorname{spf}(n), 则 n/pn/p 一定是最小的真因数 11 之外最大的那一个: 若还有真因数 d>n/pd > n/p,那么 n/d<pn/d < p 也是 nn 的因数,与 pp 是最小质因子矛盾。 所以每个合数 nn 的贡献只有 np\dfrac{n}{p} 这一项,"最大真因数"这个说法本身可以直接删掉。

朴素做法与瓶颈。 最直接的是线性筛(欧拉筛)预处理出 1∼r1 \sim r 每个数的最小质因子, 一边筛一边把合数的 n/pn/p 累加进前缀和,最后输出两个前缀之差,O(r)O(r) 时间、O(r)O(r) 空间。 r≤107r \le 10^7 时它轻松通过前 6 个测试点;但第 8、10 个测试点 r≤5×109r \le 5 \times 10^9, 数组要开 5×1095 \times 10^9 个元素(十几 GB),时间也远超 2 s。 注意第 8 个测试点是 l=1, r=5×109l = 1,\ r = 5 \times 10^9 的整个前缀区间, “只筛 [l,r][l, r]” 的区间筛在这里没有任何可省的余地。 瓶颈很清楚:我们被迫显式枚举了每一个数,而真正需要枚举的东西少得多。

关键观察:最小质因子的种类极少。 合数 n≤Nn \le N 必有 spf⁡(n)≤n≤N\operatorname{spf}(n) \le \sqrt{n} \le \sqrt{N}。 当 N=5×109N = 5 \times 10^9 时 N≈70710\sqrt{N} \approx 70710,这段范围内的质数只有 7004 个。 换句话说,全部合数只能按 7004 种最小质因子分类。

于是把合数按最小质因子分组来数:对固定的质数 pp,最小质因子恰为 pp 的合数都能唯一写成

n=p⋅m,p≤m≤⌊Np⌋,spf⁡(m)≥p, n = p \cdot m, \qquad p \le m \le \left\lfloor \frac{N}{p} \right\rfloor, \qquad \operatorname{spf}(m) \ge p ,

(m≥pm \ge p 保证 nn 是合数,spf⁡(m)≥p\operatorname{spf}(m) \ge p 保证 pp 真的是 nn 的最小质因子。) 这一组合数的贡献之和就是商 mm 的和,即

∑p≤N    ∑p≤m≤⌊N/p⌋spf⁡(m)≥pm. \sum_{p \le \sqrt{N}} \;\; \sum_{\substack{p \le m \le \lfloor N/p \rfloor \\ \operatorname{spf}(m) \ge p}} m .

到这里问题变成:对每个 p≤Np \le \sqrt{N},求 1∼⌊N/p⌋1 \sim \lfloor N/p \rfloor 中剔除所有小于 pp 的质数的倍数之后剩余元素的和。 这正是埃氏筛的作用,只是我们关心的不是"剩了哪些数",而是"剩下的数之和"。

用埃氏筛 DP 把"剩下的和"滚出来。 令 gj(w)g_j(w) 表示 2∼w2 \sim w 中质数或最小质因子 >pj−1> p_{j-1} 的数之和, 即筛掉前 j−1j-1 个质数的倍数后剩下的数值和(pip_i 表示第 ii 个质数)。初始时一个质数都没筛, 2∼w2 \sim w 全体保留:

g1(w)=2+3+⋯+w=w(w+1)2−1. g_1(w) = 2 + 3 + \cdots + w = \frac{w(w+1)}{2} - 1 .

(减去 11 是把 11 摘出去;11 既不是质数也不是合数,从头到尾都不参与统计, 所以 gg 里始终只有 ≥2\ge 2 的数,取答案时不必再处理 m=1m = 1 的边界。) 从 pj−1p_{j-1} 跨到 pjp_j 时,被新划去的数是 pjmp_j m(m≥pjm \ge p_j 且 spf⁡(m)≥pj\operatorname{spf}(m) \ge p_j),其和恰为 pj(gj(⌊w/pj⌋)−spj−1)p_j \big( g_j(\lfloor w/p_j \rfloor) - sp_{j-1} \big),其中 spj−1=p1+⋯+pj−1sp_{j-1} = p_1 + \cdots + p_{j-1} 是要从 gj(⌊w/pj⌋)g_j(\lfloor w/p_j \rfloor) 里扣掉的小于 pjp_j 的质数:筛掉前 j−1j-1 个质数的倍数之后, 这些质数仍然留在 gjg_j 里,但它们作为 mm 只会给出 n=pjmn = p_j m, 其最小质因子其实是那个更小的 qq,不属于第 jj 组,所以要减掉。 因此

gj+1(w)=gj(w)−pj(gj ⁣(⌊wpj⌋)−spj−1). g_{j+1}(w) = g_j(w) - p_j \Big( g_j\!\left(\left\lfloor \frac{w}{p_j} \right\rfloor\right) - sp_{j-1} \Big) .

只有 w≥pj2w \ge p_j^2 时才需要转移:w<pj2w < p_j^2 意味着 ⌊w/pj⌋<pj\lfloor w/p_j \rfloor < p_j,这一段里已经不存在以 pjp_j 为最小质因子的数了。

答案怎么取。 把上面的求和式代进去:对每个 pj≤Np_j \le \sqrt{N}, 第 jj 组合数(最小质因子恰为 pjp_j)的贡献就是 gj(⌊N/pj⌋)−spj−1g_j(\lfloor N/p_j \rfloor) - sp_{j-1}——仍然留在 gg 里的那些数恰好是「质数或 spf⁡≥pj\operatorname{spf} \ge p_j」, 扣掉小于 pjp_j 的质数之后剩下的正是合法的商 mm(m≥pjm \ge p_j 自动成立,因为 2≤m<pj2 \le m < p_j 的数要么有 spf⁡<pj\operatorname{spf} < p_j 已被筛走,要么本身就是被扣掉的质数)。合并即有

F(N)  =  ∑pj≤N(gj ⁣(⌊Npj⌋)−spj−1),S(l,r)=F(r)−F(l−1). F(N) \;=\; \sum_{p_j \le \sqrt{N}} \left( g_j\!\left(\left\lfloor \frac{N}{p_j} \right\rfloor\right) - sp_{j-1} \right), \qquad S(l, r) = F(r) - F(l-1) .

这也是实现里直接 ans += d(d=g−spj−1d = g - sp_{j-1})的原因:gg 已经摘掉了 11,不必再减一次。

状态只有 2N2\sqrt{N} 个。 需要转移的状态永远是 w=⌊N/i⌋w = \lfloor N/i \rfloor 这种形状, 取值不超过 2N≈1414212\sqrt{N} \approx 141421 个。把 w>Nw > \sqrt{N} 的状态按 ii 编号放进 g1[i] (此时 w=⌊N/i⌋w = \lfloor N/i \rfloor,i≤N/(N+1)i \le N/(\sqrt{N}+1) 恰好覆盖所有这种状态), w≤Nw \le \sqrt{N} 的状态直接拿 ww 当下标放进 g2[w]; 查询 gj(⌊w/p⌋)g_j(\lfloor w/p \rfloor) 时看 ⌊w/p⌋\lfloor w/p \rfloor 落在哪一半即可,无需哈希表。

为什么是 O(N3/4/log⁡N)O(N^{3/4}/\log N)。 转移次数等于满足 pj2≤wp_j^2 \le w 的 (质数, 状态) 对的数量, 按 min_25 筛的标准分析为 O(N3/4/log⁡N)O(N^{3/4}/\log N),N=5×109N = 5 \times 10^9 时约几百万次, 实测不到 30 ms,离 2 s 的时限很远。空间只要 O(N)O(\sqrt{N}),约 3 MB。

实现要点。 三条容易踩的坑:

  1. 必须用高精度整数。 g1g_1 的初值是 w(w+1)2−1\frac{w(w+1)}{2} - 1,先算 w(w+1)w(w+1) 的话 w=5×109w = 5 \times 10^9 时约 2.5×10192.5 \times 10^{19},直接超出 64 位;即使按 w(w+1)/2−1w(w+1)/2 - 1 先除后减, 结果 1.25×10191.25 \times 10^{19} 也已接近 unsigned long long 上限、且远超市面上 long long 的 9.2×10189.2 \times 10^{18}。所以本题的 main.cpp 里 g1、g2、ans、sp 全用 __int128, 最后手写 128 位输出。答案本身最大只有 4.1×10184.1 \times 10^{18}(即样例 5 风格的点), 落在 long long 内,但中间量不落在,所以不能省。
  2. g2 必须倒序更新。 转移要读 gj(⌊w/p⌋)g_j(\lfloor w/p \rfloor),而 ⌊w/p⌋<w\lfloor w/p \rfloor < w。 g2 按下标递增访问,所以从大到小扫,读到的才是上一阶段的旧值; g1 是递减的 ww,从小 ii 往大 ii 扫,⌊w/p⌋\lfloor w/p \rfloor 对应的 g1g1 下标更大、还没被更新,天然安全。
  3. N<4N < 4 直接返回 0。 此时区间里没有合数;l=1l = 1 时 l−1=0l - 1 = 0 也要能吃下。

说明:本题在仓库素材源(new_ROJ/problems/1804/)里带有自造数据生成脚本 data.py 与 config.json,data/ 是据此生成的 10 个点,题面文本与"信息学奥赛一本通·高手训练篇" 同源(该题即 FJWC2018 / BZOJ 5244《最大真因数》)。因此数据规模与官方原题可能不完全一致, 题解以本仓库 data/ 为准。素材里的 std.cpp 与本文结论一致(同样按最小质因子分组做 min_25 筛), 但它用 __int128 存全部状态且在 i=1i=1 处累加贡献,本文的 main.cpp 是独立实现。

代码

Python 短解法:

python
#!/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-08 04:13
# update_at: 2026-10-08 04:13

import sys
from itertools import accumulate
from math import isqrt

type Primes = list[int]     # 不超过 sqrt(N) 的质数,升序
type Prefix = list[int]     # sp[j] = 前 j 个质数之和


def build_primes(limit: int) -> tuple[Primes, Prefix]:
    """线性筛出 [2, limit] 的质数,并给出质数前缀和。"""
    comp = bytearray(limit + 1)
    primes: Primes = []
    for i in range(2, limit + 1):
        if not comp[i]:
            primes.append(i)
        for p in primes:                        # 线性筛:每个合数只被最小质因子划去
            if i * p > limit:
                break
            comp[i * p] = 1
            if i % p == 0:
                break
    return primes, [0, *accumulate(primes)]


def comp_sum(n: int) -> int:
    """返回 [1, n] 内所有合数的最大真因数之和。

    合数 c 的最大真因数 = c / spf(c)(spf 为最小质因子)。按 spf=p 把合数分组后,
    第 p 组的贡献 Σm 恰好是 min_25 筛里被 p 划去的那些数之和再除以 p,
    所以只需要滚动维护 g[w] = 「质数或最小质因子 > 已筛质数」的 2..w 数值和。
    """
    if n < 4:
        return 0                                # 1、2、3 都不是合数
    S = isqrt(n)
    primes, sp = build_primes(S)
    # 状态值 val = floor(n/i) 只会取 2*sqrt(n) 个值:val > S 的按 i 存进 g1,
    # val <= S 的直接拿 val 当下标存进 g2;i = 1..n//(S+1) 恰好覆盖所有 val > S。
    L = n // (S + 1)
    g1 = [0, *[(n // i) * (n // i + 1) // 2 - 1 for i in range(1, L + 1)]]
    g2 = [x * (x + 1) // 2 - 1 for x in range(S + 1)]

    ans = 0
    for j, p in enumerate(primes, 1):
        pre = sp[j - 1]                         # 小于 p 的质数之和,即 g 里要留下的质数部分
        p2 = p * p
        for i in range(1, min(L, n // p2) + 1):  # 只有 val >= p^2 的状态才含 p 的倍数
            k = i * p                           # 状态 n//i 除以 p 之后对应 floor(n/k)
            cur = g1[k] if k <= L else g2[n // k]
            d = cur - pre
            if i == 1:
                ans += d                        # 状态 n:最小质因子恰为 p 的合数贡献 Σm
            g1[i] -= d * p
        for x in range(S, p2 - 1, -1):          # 倒序保证读到的是上一阶段的 g2[x//p]
            g2[x] -= (g2[x // p] - pre) * p
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    l, r = next(data), next(data)
    print(comp_sum(r) - comp_sum(l - 1))        # 前缀和作差,区间内每个合数贡献不变


if __name__ == "__main__":
    solve()

C++ 正式解:

cpp
/**
 * 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-08 04:13
 * update_at: 2026-10-08 04:13
 */
// 一本通 1804《最大真因数》
// 合数 n 的最大真因数 = n / spf(n)(spf 为最小质因子),因为拿掉最小质因子后剩下的商最大。
// 于是答案 = F(r) - F(l-1),其中 F(N) = Σ_{合数 c<=N} c / spf(c)。
// min_25 筛取权值 f(x)=x 求 F:把合数按最小质因子 p_j 分组,第 j 组是 n = p_j*m
// (m ∈ [p_j, N/p_j] 且 spf(m) >= p_j),每组贡献恰是 Σm,正是筛过程中被 p_j 划去的那些数除以 p_j 的和。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

const int MAXS = 100005; // sqrt(5*10^9) ≈ 70710,留足余量

bool vis[MAXS];  // 线性筛的合数标记
ll prime[MAXS];  // prime[1..tot]:不超过 sqrt(N) 的质数,升序
lll sp[MAXS];    // sp[j] = 前 j 个质数之和(即「小于 p_{j+1} 的质数和」)
lll g1[MAXS];    // 大状态:下标 i=1..L,状态值 val = n/i > sqrt(n)
lll g2[MAXS];    // 小状态:下标就是状态值 x <= sqrt(n)
int tot;         // 质数个数

// 精确求 floor(sqrt(n)):先浮点开方再整数修正(n <= 5*10^9)
ll isqrt_ll(ll n) {
    ll x = sqrtl((long double)n);
    while (x > 0 && x * x > n) --x;
    while ((x + 1) * (x + 1) <= n) ++x;
    return x;
}

// 线性筛出 [2, lim] 的质数,并递推前缀和 sp
void build_prime(ll lim) {
    tot = 0;
    for (ll i = 0; i <= lim; i++) vis[i] = false;
    for (ll i = 2; i <= lim; i++) {
        if (!vis[i]) {
            prime[++tot] = i;
            sp[tot] = sp[tot - 1] + i;
        }
        for (int j = 1; j <= tot && i * prime[j] <= lim; j++) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

// g[i] 的含义:状态值 w 下「质数 或 最小质因子 > 已筛质数」的所有数值和。
// 初始(一个质数都没筛)就是 2..w 的数值和 w(w+1)/2 - 1。
// 筛 p 时被划去的数是 p*m(m >= p 且 spf(m) >= p),其和 = p*(g(w/p) - sp[小于p的质数和])。
// 状态只有 floor(N/i) 这 2*sqrt(N) 个:值 > S 的按 n/i 存进 g1,值 <= S 的直接用值当下标存 g2。

// F(n) = Σ_{合数 c<=n} c / spf(c)
lll F(ll n) {
    if (n < 4) return 0;          // 1、2、3 都不是合数
    ll S = isqrt_ll(n);
    build_prime(S);
    ll L = n / (S + 1);           // 大状态个数:状态值 n/i > S 的 i 恰好是 1..L
    for (ll i = 1; i <= L; i++) {
        lll v = n / i;
        g1[i] = v * (v + 1) / 2 - 1;
    }
    for (ll x = 1; x <= S; x++) {
        lll v = x;
        g2[x] = v * (v + 1) / 2 - 1;
    }
    lll ans = 0;
    for (int j = 1; j <= tot; j++) {
        ll p = prime[j], p2 = p * p;
        lll pre = sp[j - 1];          // 小于 p 的质数之和
        ll hb = min(L, n / p2);       // 大状态里值 >= p^2 的个数,更小的状态无 p 的倍数可划
        for (ll i = 1; i <= hb; i++) {
            ll id = i * p;            // 状态值 n/i 再除以 p,即 floor(n/(i*p))
            lll cur = (id <= L) ? g1[id] : g2[n / id];
            lll d = cur - pre;
            if (i == 1) ans += d;     // i==1 是状态 n:最小质因子恰为 p 的合数贡献 Σm
            g1[i] -= d * p;
        }
        // 小状态倒序处理,保证读到的 g2[x/p] 还是上一阶段的值(x/p < x 未被本轮更新)
        for (ll x = S; x >= p2; x--) g2[x] -= (g2[x / p] - pre) * p;
    }
    return ans;
}

// 输出 128 位整数:逐位取余打印
void print_lll(lll x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print_lll(x / 10);
    putchar('0' + (int)(x % 10)); // 取值必在 0..9,转成 int 才能参与字符运算
}

int main() {
    ll l, r;
    if (scanf("%lld %lld", &l, &r) != 2) return 0;
    print_lll(F(r) - F(l - 1));
    putchar('\n');
    return 0;
}

复杂度

  • 时间:O ⁣(N3/4log⁡N)O\!\left(\dfrac{N^{3/4}}{\log N}\right),其中 N=rN = r;常数部分是 2N2\sqrt{N} 个状态上的 埃氏筛转移。N=5×109N = 5 \times 10^9 时实际转移数百万次,C++ 实测 < 30 ms, Python 实测约 1.2 s(本题允许 Python 慢,算法与 C++ 同阶,未做任何降级)。
  • 空间:O(N)O(\sqrt{N})。N=5×109N = 5\times10^9 时状态数 2N≈1.4×1052\sqrt{N} \approx 1.4 \times 10^5, 质数表 7004 个,共计几 MB,远低于 512 MB。

总结

  • 先把"最大真因数"翻译成 n/spf⁡(n)n / \operatorname{spf}(n),题目里"真因数""最大"这些字眼就没有了, 剩下的只是一个关于最小质因子的求和。
  • 计数对象从"数"换成"最小质因子":合数只有 N\sqrt{N} 以内的质数那么多种最小质因子, 这一步是全部优化的来源。凡是 NN 很大而"每个数的某个局部特征只取少数几种值"的题, 都值得先做这个转换。
  • 埃氏筛的 DP 视角:gj+1(w)=gj(w)−pj(gj(⌊w/pj⌋)−spj−1)g_{j+1}(w) = g_j(w) - p_j\big(g_j(\lfloor w/p_j \rfloor) - sp_{j-1}\big) 把"二次筛"变成了"筛掉的部分用上一阶段的值直接算",这就是 min_25 筛的核心, 也是它能把状态压缩到 2N2\sqrt{N} 个的原因。
  • 溢出比超时更容易翻车:w=5×109w = 5 \times 10^9 时 w(w+1)/2w(w+1)/2 已在 64 位边界, 只需 gg 数组用 128 位、最终答案用 64 位输出即可,不必全盘 128 位。