思路与算法

设合数 $z$ 的最小质因子为 $p$，则最大真因数恰为 $z/p$。令 $F(N)$ 为 $[1,N]$ 内合数最大真因数之和，答案是 $F(r)-F(l-1)$。按最小质因子 $p$ 分类，写成 $z=pq$，其中 $q\ge p$，且 $q$ 没有小于 $p$ 的质因子。此类贡献就是所有这些 $q$ 的和。

只保存所有不同商值 $v=\lfloor N/i\rfloor$。初始 $g(v)=2+3+\cdots+v$。按质数从小到大筛，处理 $p$ 之前，$g(v)$ 保存小于 $p$ 的质数以及最小质因子不小于 $p$ 的整数之和。记此前质数之和为 $P$，则最小质因子恰为 $p$ 的合数贡献为 $g(\lfloor N/p\rfloor)-P$，先加入答案，再对所有 $v\ge p^2$ 更新 $g(v)\leftarrow g(v)-p(g(\lfloor v/p\rfloor)-P)$。商值从大到小更新，保留本轮读取的旧状态。最后把 $p$ 加入 $P$。只需枚举到 $\sqrt N$。

用线性筛生成质数，商值分为不超过平方根和较大两类，分别通过 $v$ 和 $N/v$ 常数时间定位。所有求和与乘法均用 __int128，最后按十进制输出。

正确性说明

首先，合数 $z$ 的因数与余因数配对。最大真因数对应最小且大于1的余因数，这个余因数必为最小质因子，故最大真因数是 $z/p$。

筛状态不变量初始显然成立。轮到 $p$ 时，待删合数唯一写成 $p q$，$q\ge p$ 且不含更小质因子。$g(\lfloor v/p\rfloor)$ 中小于 $p$ 的质数之和恰为 $P$，减去后正好得到这些 $q$ 的和；乘 $p$ 后删掉全部最小质因子为 $p$ 的合数，同时保留质数 $p$。这保持下一轮不变量。大商值优先更新保证右侧未在本轮删去 $p$ 的倍数。

同一分类在上界 $N$ 处给出的 $q$ 之和，就是该类最大真因数之和。每个合数有唯一最小质因子且该质因子不超过平方根，故各轮贡献不重不漏，且未加入质数贡献。前缀差因此正确。

复杂度

设 $R=r$。不同商值数是 $O(\sqrt R)$，初始化及质数线性筛均为 $O(\sqrt R)$。加权商值筛采用逐质数遍历 $v\ge p^2$ 的标准筛更新，复杂度 $O(R^{3/4}/\log R)$，也可用更宽松的 $O(R^{3/4})$ 上界；求两次前缀只增加常数。空间 $O(\sqrt R)$。题目上界为 $5\times10^9$，128位整数覆盖全部中间量。

易错点

题目只统计合数，不给质数加1。$N<4$ 直接返回0；数字1不属于合数。必须先累计当前质数的贡献，再修改筛状态。不能把最大真因数当成所有真因数之和；也不能只用短区间分段筛而漏掉公开的宽区间样例。平方界、三角数和加权更新须先转换宽整数再乘。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128_t;
i128 prefix(i64 n) {
    if (n < 4)
        return 0;
    int s = sqrt((long double)n);
    while (1LL * (s + 1) * (s + 1) <= n)
        ++s;
    while (1LL * s * s > n)
        --s;
    vector<int> primes;
    vector<bool> composite(s + 1);
    for (int p = 2; p <= s; ++p) {
        if (!composite[p])
            primes.push_back(p);
        for (int q : primes) {
            if (1LL * p * q > s)
                break;
            composite[p * q] = true;
            if (p % q == 0)
                break;
        }
    }
    vector<i64> values;
    vector<int> low(s + 1), high(s + 1);
    for (i64 l = 1, r; l <= n; l = r + 1) {
        i64 v = n / l;
        r = n / v;
        int id = values.size();
        values.push_back(v);
        if (v <= s)
            low[v] = id;
        else
            high[n / v] = id;
    }
    auto index = [&](i64 v) {
        return v <= s ? low[v] : high[n / v];
    };
    vector<i128> sum(values.size());
    for (size_t i = 0; i < values.size(); ++i)
        sum[i] = (i128)values[i] * (values[i] + 1) / 2 - 1;
    i128 answer = 0, previous = 0;
    for (int p : primes) {
        answer += sum[index(n / p)] - previous;
        i64 square = 1LL * p * p;
        for (size_t j = 0; j < values.size() && values[j] >= square; ++j)
            sum[j] -= (i128)p * (sum[index(values[j] / p)] - previous);
        previous += p;
    }
    return answer;
}
void print(i128 x) {
    if (x >= 10)
        print(x / 10);
    cout << char('0' + x % 10);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 l, r;
    if (cin >> l >> r) {
        print(prefix(r) - prefix(l - 1));
        cout << '\n';
    }
}