2300. 皇家魔导士的能量纯度评估
1000ms
256MB
简单
简单数学
题目描述
在魔法大陆上，每一块魔法水晶的能量值都是由若干个不可分割的“魔法基石”（质因子）通过相乘形成的。一块魔法水晶所包含的“魔法基石”总个数（包含重复的基石，例如能量值为 $8$ 的水晶，其基石为 $2 \times 2 \times 2$，共含有 3 个基石）代表了它的“能量核纯度”。
现在给定魔法水晶的编号区间 $[N, M]$，请你编写程序统计该区间内（含 $N$ 和 $M$）每个数包含的质因数个数（含重复值），并输出其中最大的个数。
输入格式
一行，包含两个正整数 $N$ 和 $M$ ($2 \le N \le M \le 10^6$)，两个正整数之间用一个空格隔开。
输出格式
输出一行，一个整数，表示在区间 $[N, M]$ 之间质因数个数的最大值。
样例 1
输入 (Input)
6 10
输出 (Output)
3
- 对于所有数据：$2 \le N \le M \le 10^6$。
- **样例说明**：
在区间 $[6, 10]$ 之间：
- $6 = 2 \times 3$，质因数有 2 个；
- $7 = 7$，质因数有 1 个；
- $8 = 2 \times 2 \times 2$，质因数有 3 个；
- $9 = 3 \times 3$，质因数有 2 个；
- $10 = 2 \times 5$，质因数有 2 个；
- 质因数个数最多的是 $8$，有 3 个，因此输出 3。
- **算法提示**：
如果对区间内的每一个数单独进行质因数分解，时间复杂度会退化到 $O(M \sqrt{M})$，在 $M = 10^6$ 时会面临超时（TLE）的风险。
建议使用**线性筛法（如欧拉筛）**在 $O(M)$ 的时间复杂度内，预处理出 $1$ 到 $M$ 所有数的最小质因子，然后利用动态规划（DP）思想完成递推：
$$dp[i] = dp[i / min\_prime[i]] + 1$$
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功