思路与算法

把largest[0..n]初始化为0。递增枚举p，若largest[p]为0，则p是素数，把p的所有倍数的值覆盖成p。所有素数按从小到大处理，所以最终留下每个数的最大质因子。输出m到n的值，逗号分隔。

正确性说明

若p为合数，它已有更小质因子，之前已被标记；素数p不会被更小素数整除，故仍为0，所以筛选出的p恰为素数。每次写入恰好覆盖含p因子的所有数。因素数递增，每个数最后被其最大质因子覆盖；素数自身被写成自身。遍历闭区间即可得到全部答案。

复杂度

初始化O(n)，标记素数倍数O(n log log n)，输出O(n-m+1)，总时间O(n log log n)，空间O(n)。1<m<n<=5000，各数均有质因子。

易错点

这里每个素数从自身开始标记，不能从平方开始，否则素数自己的值仍为0。必须覆盖已有值才能得到最大质因子。包含两端点，输出用英文逗号，首尾无逗号。

参考代码（C++11）

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int m, n;
    cin >> m >> n;
    vector<int> largest(n + 1, 0);
    for (int p = 2; p <= n; ++p)
        if (largest[p] == 0)
            for (int v = p; v <= n; v += p)
                largest[v] = p;
    for (int v = m; v <= n; ++v) {
        if (v != m)
            cout << ',';
        cout << largest[v];
    }
    cout << '\n';
}