【Fjwc2018】最大真因数

## 【Fjwc2018】最大真因数 ### 题目描述 设 $f(x)=\max_{d}[d|x] \cdot [d \ne x] \cdot [d \ne 1] \cdot d$，如果不存在 $d$ 则 $f(x)=0$ 给定 $l,r$，求： $$\sum_{i=l}^{r}f(i)$$ 其中 $1 \le l \le r \le 5 \times 10^9$ ### 题解 由于 $f(x)=\frac{x}{\text{mind}(x)}$，其中 $\text{mind}(x)$ 表示 $x$ 的最小质因子，考虑 $\text{min\_25}$ 筛的过程： $$g(\frac{n}{p_j},j-1)-\sum_{i=1}^{j-1}p_i$$ 那么这部分就是最小质因子为 $p_j$ 的那些数字的除以 $p_j$ 后的值，也就是要求的 $f(x)$ 之和 于是在 $\text{min\_25}$ 筛的时候统计一下就行了