修复：
[update 2025/10/20 17:18] 修改一处文本，但不影响理解 \text{[update 2025/10/20 17:18] 修改一处文本，但不影响理解} [update 2025/10/20 17:18] 修改一处文本，但不影响理解
[update 2025/10/20 18:17] 修改三处标题，但不影响理解 \text{[update 2025/10/20 18:17] 修改三处标题，但不影响理解} [update 2025/10/20 18:17] 修改三处标题，但不影响理解
Parts1: Min_25: 简单来说，Min_25 是一种快速求一个积性函数
f ( x ) f(x) f ( x ) 前缀和的筛法，对于这个
f ( x ) f(x) f ( x ) ， 我们有以下要求和限制：
首先对于 f ( p ) f(p) f ( p ) p p p
其次对于 f ( p k ) f(p^k) f ( p k ) p p p
那么到底怎么做呢，我们现在来说。首先，我们考虑将质数部分先处理掉，定义一个辅助函数
g ( n , j ) g(n,j) g ( n , j ) , 其定义为在埃拉托斯特尼筛法，也就是埃氏筛中未被前
j j j 个质数筛掉（即最小质因子 >
p j p_j p j ）的数的
f ′ ( x ) f'(x) f ′ ( x ) 之和，这里为了后面的讲解，使用一个完全积性函数
f ′ ( x ) f'(x) f ′ ( x ) 近似原函数
f ( x ) f(x) f ( x ) 在质数位置的值。现在我们容易得出，对于
g ( n , 0 ) g(n,0) g ( n , 0 ) 有：
g ( n , 0 ) = ∑ i = 2 n f ′ ( i ) g(n,0) = \sum_{i=2}^n f'(i) g ( n , 0 ) = i = 2 ∑ n f ′ ( i ) 考虑如果
f ′ ( i ) f'(i) f ′ ( i ) 是一个简单多项式的化，我们可以直接用公式求和。接下来对于所有
g ( n , j ) g(n,j) g ( n , j ) 我们考虑从
g ( n , 0 ) g(n,0) g ( n , 0 ) 推广得出以下递推式：
g ( n , j ) = { g ( n , j − 1 ) − f ′ ( p j ) ⋅ [ g ( ⌊ n p j ⌋ , j − 1 ) − ∑ i = 1 j − 1 f ′ ( p i ) ] , If p j 2 ≤ n g ( n , j − 1 ) , If p j 2 > n g(n, j) =
\begin{cases}
g(n, j-1) - f'(p_j) \cdot \left[ g\left( \left\lfloor \frac{n}{p_j} \right\rfloor, j-1 \right) - \sum_{i=1}^{j-1} f'(p_i) \right], & \text{If } p_j^2 \le n \\
g(n, j-1), & \text{If } p_j^2 > n
\end{cases} g ( n , j ) = { g ( n , j − 1 ) − f ′ ( p j ) ⋅ [ g ( ⌊ p j n ⌋ , j − 1 ) − ∑ i = 1 j − 1 f ′ ( p i ) ] , g ( n , j − 1 ) , If p j 2 ≤ n If p j 2 > n 对于
g ( n , j ) g(n,j) g ( n , j ) 的上限，我们认为
j j j 应该尽可能取到一个与
n \sqrt{n} n 最接近且严格大于其的质数，然后我们就会发现这个极限的
g ( n , j ) g(n,j) g ( n , j ) 就是对于所有
p ≤ n p \le n p ≤ n 且
p p p 为质数情况下，
f ′ ( p ) f'(p) f ′ ( p ) 之和，搞定！接下来考虑计算合数部分，我们定义一个
s ( n , i ) s(n,i) s ( n , i ) 表示所有最小质因子大于
p i p_i p i 的数的
f ( i ) f(i) f ( i ) 之和。那么我们的目标就是计算
s ( n , 0 ) s(n,0) s ( n , 0 ) ，最后加上
f ( 1 ) f(1) f ( 1 ) (如果需要的话), 我们考虑
s ( n , i ) s(n,i) s ( n , i ) 递归式为
S ( n , i ) = ( g ( n , j max ) − ∑ j = 1 j f ( p j ) ) + ∑ k > i ∑ e ≥ 1 [ f ( p k e ) ⋅ ( S ( ⌊ n p k e ⌋ , k ) + [ e > 1 ] ) ] S(n,i) = (g(n,j_{\max}) - \sum_{j = 1}^j f(p_j)) + \sum_{k > i} \sum_{e \ge 1} [f(p_k^e) \cdot (S(\lfloor \frac{n}{p^e_k}\rfloor , k) + [e > 1])] S ( n , i ) = ( g ( n , j m a x ) − j = 1 ∑ j f ( p j )) + k > i ∑ e ≥ 1 ∑ [ f ( p k e ) ⋅ ( S (⌊ p k e n ⌋ , k ) + [ e > 1 ])] 其中我们计算的是所有大于
p i p_i p i 的质数的
f ( p ) f(p) f ( p ) 的和，后面的那个一长串二重求和是枚举合数的最小质因子
p k p_k p k ，以及其指数。然后
S ( ⌊ n p k e ⌋ , k ) S(\lfloor \frac{n}{p^e_k}\rfloor , k) S (⌊ p k e n ⌋ , k ) 表示递归计算除去最小质因子
p k e p_k^e p k e 后剩余部分（其最小质因子大于
p k p_k p k ） 的
f f f 值。然后后面的
[ e > 1 ] [e > 1] [ e > 1 ] 是一个指示函数，主要是考虑
p k e p_k^e p k e 本身用的。
递归边界为
n < p i n < p_i n < p i 时满足
s ( n , i ) = 0 s(n,i) = 0 s ( n , i ) = 0 ， 最终就是
∑ i = 1 n f ( i ) = s ( n , 0 ) + f ( 1 ) \sum_{i = 1}^n f(i) = s(n,0) + f(1) ∑ i = 1 n f ( i ) = s ( n , 0 ) + f ( 1 ) 。
现在我们考虑证明 Min_25 时间复杂度，先证明对于所有
S ( m , i ) S(m,i) S ( m , i ) ， 其中
m m m 只有最多
n \sqrt{n} n 种取值，原因非常简单，在计算
S ( n , i ) S(n,i) S ( n , i ) 的时候，参数
m m m 总是形如
⌊ n k ⌋ \lfloor \frac{n}{k} \rfloor ⌊ k n ⌋ ，就是数论分块的证明。当然这个是小菜，我们接下来质数分布的估计，需要前置知识切比雪夫定理，也就是我们规定对于第
k k k 个质数
p k ∼ k ln k p_k \sim k \ln k p k ∼ k ln k 且
π ( n ) ∼ n ln n \pi(n) \sim \frac{n}{\ln n} π ( n ) ∼ l n n n 。这个就是定理，非常简单，而且根据上面的递推式，也很好证明
S ( m , i ) S(m,i) S ( m , i ) 所有有意义的
i i i 满足
p i ≤ m p_i \le \sqrt{m} p i ≤ m 。
然后现在我们说， Min_25 时间复杂度为
O ( n 3 4 log n ) O(\frac{n^{\frac{3}{4}}}{\log n}) O ( l o g n n 4 3 ) 级别的，我们分析递归计算
S ( m , i ) S(m,i) S ( m , i ) 的总代价，我们定义
V = { ⌊ n k ⌋ : 1 ≤ k ≤ n } V = \{\left\lfloor \frac{n}{k} \right\rfloor : 1 \le k \le n\} V = { ⌊ k n ⌋ : 1 ≤ k ≤ n } , 然后根据
p i p_i p i 与
m m m 的大小关系，分为：
Case 1: p i ≤ m 1 4 p_i \le m^{\frac{1}{4}} p i ≤ m 4 1 Case 2: m 1 4 < p i ≤ n m^{\frac{1}{4}} < p_i \le \sqrt{n} m 4 1 < p i ≤ n
现在我们逐步分析：
对于 Case 1 的，我们有：首先，根据递归式，我们知道 m m m n \sqrt{n} n m m m p i ≤ m 1 4 p_i \le m^{\frac{1}{4}} p i ≤ m 4 1 i i i π ( m 1 4 ) = O ( m 1 4 log n ) \pi(m^{\frac{1}{4}}) = O(\frac{m^{\frac{1}{4}}}{\log n}) π ( m 4 1 ) = O ( l o g n m 4 1 ) Case 1 是一个小部分，我们忽略不计。
接下来对于 Case 2 这个关键的地方，我们做以下事情：首先由递归式可以快速推导出我们在考虑上面的东西时，只需要考虑 e = 1 e = 1 e = 1 S ( m , i ) S(m,i) S ( m , i ) Case 2)， 产生的调用总次数为 π ( m ) − i \pi(\sqrt{m}) - i π ( m ) − i T ( m , i ) T(m,i) T ( m , i ) S ( m , i ) S(m,i) S ( m , i )
T ( m , i ) = 1 + ∑ k > i p k ≤ m T ( ⌊ m p k ⌋ , k ) T(m, i) = 1 + \sum_{\substack{k > i \\ p_k \le \sqrt{m}}} T(\lfloor \frac{m}{p_k} \rfloor, k) T ( m , i ) = 1 + k > i p k ≤ m ∑ T (⌊ p k m ⌋ , k ) 但是我们关心的时
T ( n , 0 ) T(n,0) T ( n , 0 ) ，可以尝试使用积分近似，有：
∑ m ∈ V m ≥ n 1 2 [ π ( m ) − π ( m 1 4 ) ] ∼ ∑ m ∈ V m ≥ n 1 2 [ 2 m log m − 4 m 1 4 log m ] \sum_{\substack{m \in V \\ m \ge n^{\frac{1}{2}}}} [\pi(\sqrt{m}) - \pi(m^{\frac{1}{4}})]
\sim \sum_{\substack{m \in V \\ m \ge n^{\frac{1}{2}}}} \left[ \frac{2\sqrt{m}}{\log m} - \frac{4m^{\frac{1}{4}}}{\log m} \right] m ∈ V m ≥ n 2 1 ∑ [ π ( m ) − π ( m 4 1 )] ∼ m ∈ V m ≥ n 2 1 ∑ [ log m 2 m − log m 4 m 4 1 ] ∫ n 1 2 n ( 2 x log x − 4 x 1 4 log x ) d x x \int_{n^{\frac{1}{2}}}^n \left( \frac{2\sqrt{x}}{\log x} - \frac{4x^{\frac{1}{4}}}{\log x} \right) \frac{dx}{x} ∫ n 2 1 n ( log x 2 x − log x 4 x 4 1 ) x d x 这里
d x x \frac{dx}{x} x d x 是因为
m m m 的取值密度约为
d m m \frac{dm}{m} m d m ， 然后考虑计算：
∫ n 1 2 n 2 x x log x d x = ∫ n 1 2 n 2 x 1 2 log x d x \int_{n^{\frac{1}{2}}}^n \frac{2\sqrt{x}}{x\log x} dx = \int_{n^{\frac{1}{2}}}^n \frac{2}{x^{\frac{1}{2}}\log x} dx ∫ n 2 1 n x log x 2 x d x = ∫ n 2 1 n x 2 1 log x 2 d x 然后令
t = log x t = \log x t = log x 且
d x = e t d t dx = e^tdt d x = e t d t 则：
= ∫ 1 2 log n log n 2 e t 2 t d t ∼ 4 n 1 2 log n = \int_{\frac{1}{2}\log n}^{\log n} \frac{2e^{\frac{t}{2}}}{t} dt \sim \frac{4n^{\frac{1}{2}}}{\log n} = ∫ 2 1 l o g n l o g n t 2 e 2 t d t ∼ log n 4 n 2 1 然后后面这一项太小了，直接不看，因此我们估计时间复杂度在
O ( n 3 4 log n ) O(\frac{n^{\frac{3}{4}}}{\log n}) O ( l o g n n 4 3 ) , 当然这个不是准确值，也有别的说法，但是大概在这个量级是没错的。
Part 2: Meissel-Lehmer 严格意义上来说，Meissel-Lehmer 没有 Min_25 那么实用，但是还是很棒的，我们来详细说一下，Meissel-Lehmer 是求：
π ( x ) = # { p ≤ x ∣ p is prime } \pi(x) = \#\{p \le x | p \text{ is prime}\} π ( x ) = # { p ≤ x ∣ p is prime } 你可能说，哎呀这个筛法不是轻轻松松吗，实则要是我
n n n 大一点点直接原地升天，这个时候，我们就要升级算法了，我们来说一下算法流程，首先，定义：
ϕ ( x , a ) = # { n ≤ x : p ∣ n ⟹ p > p a } \phi(x, a) = \#\{n \le x : p \mid n \implies p > p_a\} ϕ ( x , a ) = # { n ≤ x : p ∣ n ⟹ p > p a } 其中
p a p_a p a 表示第
a a a 个素数，其中
p 1 = 2 p_1 = 2 p 1 = 2 。换句话说，
ϕ ( x , a ) \phi(x,a) ϕ ( x , a ) 是
1 … x 1 \dots x 1 … x 中所有不被前
a a a 个素数整除的正整数的个数，即：用埃氏筛筛掉前
a a a 个素数后剩下的数的个数，和上面 Min_25 是差不多的（但是就是要换个说法，主要是写作时间线和参考的文献不太一样，就有些问题多多谅解）显然，这些数包括：
所有大于 p a p_a p a ≤ x \le x ≤ x
以及 1 1 1
所以容易推导得到：
π ( x ) = ϕ ( x , a ) + a − 1 , If p a ≤ x < p a + 1 . \pi(x) = \phi(x, a) + a - 1, \quad \text{If } p_a \le \sqrt{x} < p_{a+1}. π ( x ) = ϕ ( x , a ) + a − 1 , If p a ≤ x < p a + 1 . 接下来我们就要来推导
ϕ \phi ϕ 的公式了，你只需要记住有：
ϕ ( x , a ) = ϕ ( x , a − 1 ) − ϕ ( x p a , a − 1 ) \phi(x, a) = \phi(x, a-1) - \phi\left( \frac{x}{p_a}, a-1 \right) ϕ ( x , a ) = ϕ ( x , a − 1 ) − ϕ ( p a x , a − 1 ) 从
a − 1 a-1 a − 1 到
a a a 时，我们筛掉那些不被前
a − 1 a-1 a − 1 个素数整除但能被
p a p_a p a 整除的数。
这些数可以写成
p a ⋅ m p_a \cdot m p a ⋅ m ，其中
m m m 不被前
a − 1 a-1 a − 1 个素数整除，且
p a m ≤ x p_a m \le x p a m ≤ x ，即
m ≤ ⌊ x p a ⌋ m \le \lfloor \frac{x}{p_a} \rfloor m ≤ ⌊ p a x ⌋ 。
满足
m m m 不被前
a − 1 a-1 a − 1 个素数整除的个数正是
ϕ ( x p a , a − 1 ) \phi\left( \frac{x}{p_a}, a-1 \right) ϕ ( p a x , a − 1 ) 。
但是先需要定义
ϕ ( x , 0 ) = 0 \phi(x,0) = 0 ϕ ( x , 0 ) = 0 , 也就是没筛任何数的时候，所有正整数留下。
但是直接递归计算
ϕ \phi ϕ 还是无法令人接受，但是我们有一个非常关键的观察：
定义
P k ( x , a ) P_k(x,a) P k ( x , a ) 为：
P k ( x , a ) = # { n ≤ x : n = q 1 q 2 … q k , q 1 > q 2 > ⋯ > q k > p a } P_k(x, a) = \#\{ n \le x : n = q_1 q_2 \dots q_k,\ q_1 > q_2 > \dots > q_k > p_a \} P k ( x , a ) = # { n ≤ x : n = q 1 q 2 … q k , q 1 > q 2 > ⋯ > q k > p a } 取
a = π ( x 1 3 ) a = \pi(x^{\frac{1}{3}}) a = π ( x 3 1 ) ，
b = π ( x ) b = \pi(\sqrt{x}) b = π ( x ) 。
因为每个不被前
a a a 个素数整除的数
≤ 1 \le 1 ≤ 1 且所有素数大于
p a p_a p a 。
此时我们容易写出：
ϕ ( x , a ) = 1 + ∑ k = 1 ∞ P k ( x , a ) \phi(x, a) = 1 + \sum_{k=1}^\infty P_k(x, a) ϕ ( x , a ) = 1 + k = 1 ∑ ∞ P k ( x , a ) 因为每个不被前
k k k 个素数整除的
> 1 >1 > 1 的数，其所有素因子
> p a > p_a > p a ，且素因子个数
k ≥ 1 k \geq 1 k ≥ 1 。
显然我们可以打个表：
P 1 ( x , a ) = π ( x ) − a P_1(x, a) = \pi(x) - a P 1 ( x , a ) = π ( x ) − a P 2 ( x , a ) = # { p q ≤ x : p > q > p a } P_2(x, a) = \#\{ pq \le x : p > q > p_a \} P 2 ( x , a ) = # { pq ≤ x : p > q > p a } P 3 ( x , a ) = # { p q r ≤ x : p > q > r > p a } P_3(x, a) = \#\{ pqr \le x : p > q > r > p_a \} P 3 ( x , a ) = # { pq r ≤ x : p > q > r > p a }
然后瞎猜有：
ϕ ( x , a ) = 1 + [ π ( x ) − a ] + P 2 ( x , a ) + P 3 ( x , a ) + … \phi(x, a) = 1 + [\pi(x) - a] + P_2(x, a) + P_3(x, a) + \dots ϕ ( x , a ) = 1 + [ π ( x ) − a ] + P 2 ( x , a ) + P 3 ( x , a ) + … 接下来我们分开处理，取
a = π ( x 1 3 ) a = \pi(x^{\frac{1}{3}}) a = π ( x 3 1 ) ， 则：
p a + 1 > x 1 3 p_{a+1} > x^{\frac{1}{3}} p a + 1 > x 3 1 然后对于
k ≥ 3 k \geq 3 k ≥ 3 最小
P 3 P_3 P 3 对应
p a + 1 p a + 2 p a + 3 > ( x 1 3 ) 3 = x p_{a+1} p_{a+2} p_{a+3} > (x^{\frac{1}{3}})^3 = x p a + 1 p a + 2 p a + 3 > ( x 3 1 ) 3 = x 因此：
P k ( x , a ) = 0 If k ≥ 3 P_k(x, a) = 0 \quad \text{If } k \ge 3 P k ( x , a ) = 0 If k ≥ 3 所以：
ϕ ( x , a ) = 1 + π ( x ) − a + P 2 ( x , a ) \phi(x, a) = 1 + \pi(x) - a + P_2(x, a) ϕ ( x , a ) = 1 + π ( x ) − a + P 2 ( x , a ) 整理以后：
π ( x ) = ϕ ( x , a ) + a − 1 − P 2 ( x , a ) (1) \pi(x) = \phi(x, a) + a - 1 - P_2(x, a) \tag{1} π ( x ) = ϕ ( x , a ) + a − 1 − P 2 ( x , a ) ( 1 ) 然后考虑固定第
i i i 个素数，其中
a < i ≤ b = π ( x ) a < i \le b = \pi(\sqrt{x}) a < i ≤ b = π ( x ) ，有
p j > p i p_j > p_i p j > p i 使得
p i p j ≤ x p_i p_j \le x p i p j ≤ x 也就是
p j ≤ x / p i p_j \le x/p_i p j ≤ x / p i , 容易写出这样的
p j p_j p j 一共有：
π ( x p i ) − π ( p i ) \pi\left( \frac{x}{p_i} \right) - \pi(p_i) π ( p i x ) − π ( p i ) 个，但是
π ( p i ) = i \pi(p_i) = i π ( p i ) = i ，由此：
P 2 ( x , a ) = ∑ i = a + 1 b [ π ( x p i ) − i ] (2) P_2(x, a) = \sum_{i=a+1}^{b} \left[ \pi\left( \frac{x}{p_i} \right) - i \right] \tag{2} P 2 ( x , a ) = i = a + 1 ∑ b [ π ( p i x ) − i ] ( 2 ) 最后，将 (1) 和 (2) 写出来，就变成了：
π ( x ) = ϕ ( x , π ( 1 3 ) ) + π ( 1 3 ) − 1 − ∑ i = π ( x 1 3 ) + 1 π ( x ) [ π ( x p i ) − i ] \pi(x) = \phi(x, \pi(\frac{1}{3})) + \pi(\frac{1}{3}) - 1 - \sum_{i=\pi(x^{\frac{1}{3}})+1}^{\pi(\sqrt{x})} \left[ \pi\left( \frac{x}{p_i} \right) - i \right] π ( x ) = ϕ ( x , π ( 3 1 )) + π ( 3 1 ) − 1 − i = π ( x 3 1 ) + 1 ∑ π ( x ) [ π ( p i x ) − i ] 计算步骤很简单，预处理素数到
x \sqrt{x} x 然后用 DP 或别的递归方法计算
ϕ ( x , a ) \phi(x,a) ϕ ( x , a ) ， 然后计算
P 2 P_2 P 2 带入求和得到
π ( x ) \pi(x) π ( x ) 。
现在是时间复杂度证明时间！
定义计算
ϕ ( x , a ) \phi(x,a) ϕ ( x , a ) 时出现的不同第一个参数的集合为：
S = { ⌊ x n ⌋ : n = p i 1 p i 2 ⋯ p i k , i 1 > i 2 > ⋯ > i k , n ≤ x , k ≥ 0 } . S = \left\{ \left\lfloor \frac{x}{n} \right\rfloor : n = p_{i_1} p_{i_2} \cdots p_{i_k},\ i_1 > i_2 > \cdots > i_k,\ n \le x,\ k \ge 0 \right\}. S = { ⌊ n x ⌋ : n = p i 1 p i 2 ⋯ p i k , i 1 > i 2 > ⋯ > i k , n ≤ x , k ≥ 0 } . 每个
n n n 是前
a a a 个素数中若干个的乘积（无平方因子）。
有引理如
∣ S ∣ = O ( x 2 3 log 2 x ) |S| = O\left( \frac{x^{\frac{2}{3}}}{\log^2 x} \right) ∣ S ∣ = O ( l o g 2 x x 3 2 ) ，证明很简单，如下：
将
S S S 按
n ≤ x 1 3 n \le x^{\frac{1}{3}} n ≤ x 3 1 与
n > x 1 3 n > x^{\frac{1}{3}} n > x 3 1 分成两部分。
若
n ≤ x 1 3 n \le x^{\frac{1}{3}} n ≤ x 3 1 ，则
⌊ x n ⌋ ≥ x 2 3 \lfloor \frac{x}{n} \rfloor \ge x^{\frac{2}{3}} ⌊ n x ⌋ ≥ x 3 2 ，且不同的
n n n 的数量不超过
x 1 3 x^{\frac{1}{3}} x 3 1 ，因此对应的
m m m 的数量
≤ x 1 3 \le x^{\frac{1}{3}} ≤ x 3 1 。
若
n > x 1 3 n > x^{\frac{1}{3}} n > x 3 1 ，则
m = ⌊ x n ⌋ < x 2 3 m = \lfloor \frac{x}{n} \rfloor < x^{\frac{2}{3}} m = ⌊ n x ⌋ < x 3 2 。
对于固定的
m m m ，
n = ⌊ x m ⌋ n = \lfloor \frac{x}{m} \rfloor n = ⌊ m x ⌋ 唯一确定，因此这样的
m m m 的数量
≤ x 2 3 \le x^{\frac{2}{3}} ≤ x 3 2 。
但需注意
n n n 必须是无平方因子数且素因子来自前
a a a 个素数。
记
m = ⌊ x n ⌋ m = \lfloor \frac{x}{n} \rfloor m = ⌊ n x ⌋ ，则
n ≈ x m n \approx \frac{x}{m} n ≈ m x 。
当
m ≤ x 2 3 m \le x^{\frac{2}{3}} m ≤ x 3 2 时，
n ≥ x 1 3 n \ge x^{\frac{1}{3}} n ≥ x 3 1 。
对于
m ≤ x 1 2 m \le x^{\frac{1}{2}} m ≤ x 2 1 ，
n ≥ x 1 2 n \ge x^{\frac{1}{2}} n ≥ x 2 1 ，这样的
n n n 的数量由大素数积控制，可用组合数上界：
不超过
( a r ) \binom{a}{r} ( r a ) 对某个
r r r ，且
n ≥ x 1 3 n \ge x^{\frac{1}{3}} n ≥ x 3 1 时
r r r 较大，总数经细致平衡可得
O ( x 2 3 log 2 x ) O\left( \frac{x^{\frac{2}{3}}}{\log^2 x} \right) O ( l o g 2 x x 3 2 ) 。
综合两部分，
∣ S ∣ = O ( x 2 3 log 2 x ) |S| = O\left( \frac{x^{\frac{2}{3}}}{\log^2 x} \right) ∣ S ∣ = O ( l o g 2 x x 3 2 ) 。
然后又有引理有：计算
ϕ ( m , a ) \phi(m, a) ϕ ( m , a ) 对所有
m ∈ S m \in S m ∈ S 的时间为
O ( x 2 3 log 2 x ⋅ a ) O\left( \frac{x^{\frac{2}{3}}}{\log^2 x} \cdot a \right) O ( l o g 2 x x 3 2 ⋅ a ) 。
证明依旧简单，但是因为篇幅问题，不证明了。接下来证明
P 2 P_2 P 2 的时间复杂度：
P 2 = ∑ i = a + 1 b [ π ( x p i ) − i ] . P_2 = \sum_{i=a+1}^{b} \left[ \pi\left( \frac{x}{p_i} \right) - i \right]. P 2 = i = a + 1 ∑ b [ π ( p i x ) − i ] . 其中项数
b − a = π ( x ) − π ( x 1 / 3 ) = Θ ( x log x ) b-a = \pi(\sqrt{x}) - \pi(x^{1/3}) = \Theta\left( \frac{\sqrt{x}}{\log x} \right) b − a = π ( x ) − π ( x 1/3 ) = Θ ( l o g x x ) 。
需要计算每个
π ( x p i ) \pi(\frac{x}{p_i}) π ( p i x ) ， 其中
p i ≥ x 1 3 p_i \ge x^{\frac{1}{3}} p i ≥ x 3 1 , 然后考虑预计算
π ( m ) \pi(m) π ( m ) 对于所有
m ≤ x 2 3 m \le x^{\frac{2}{3}} m ≤ x 3 2 可以使用埃氏筛完成，因此
P 2 P_2 P 2 的求和耗时为：
O ( x log x ) . O\left( \frac{\sqrt{x}}{\log x} \right). O ( log x x ) . 接下来汇总：
注意到瓶颈过高，要优化（Lagarias–Miller–Odlyzko 1985） ：
通过只保留
m = ⌊ x t ⌋ m = \lfloor \frac{x}{t} \rfloor m = ⌊ t x ⌋ 对于
t ≤ x 1 3 t \le x^{\frac{1}{3}} t ≤ x 3 1 ， 则计算
ϕ \phi ϕ 的时间为：
O ( a ⋅ ∣ S ∣ ) = O ( x 1 3 log x ⋅ x 1 3 ) = O ( x 2 3 log x ) O(a \cdot |S|) = O\left( \frac{x^{\frac{1}{3}}}{\log x} \cdot x^{\frac{1}{3}} \right) = O\left( \frac{x^{\frac{2}{3}}}{\log x} \right) O ( a ⋅ ∣ S ∣ ) = O ( log x x 3 1 ⋅ x 3 1 ) = O ( log x x 3 2 ) 预计算一些小
m m m 的
ϕ \phi ϕ 可以在
O ( x 2 3 log log x ) O(x^{\frac{2}{3}} \log \log x) O ( x 3 2 log log x ) 内完成。
最后汇总得到：
O ( x 2 3 log x + x 2 3 log log x + x log x ) = O ( x 2 3 log x ) . O\left( \frac{x^{\frac{2}{3}}}{\log x} + x^{\frac{2}{3}} \log \log x + \frac{\sqrt{x}}{\log x} \right) = O\left( \frac{x^{\frac{2}{3}}}{\log x} \right). O ( log x x 3 2 + x 3 2 log log x + log x x ) = O ( log x x 3 2 ) . 如果你还是优化大佬的话，兴许可以来到：
O ( x 2 3 log 2 x ) O\left( \frac{x^{\frac{2}{3}}}{\log^2 x} \right) O ( log 2 x x 3 2 ) 还是比 Min_25 快多了。
Part3: Powerful Number 筛 Powerful Number 筛，我们也称作 PN 筛，是最近几年才出现的一种非常厉害的筛法。
定义：正整数
n n n 为 Powerful Number 当且仅当
n n n 的所有质因子
p p p 都有
p 2 ∣ n p^2 \mid n p 2 ∣ n 。
性质有下：
1 1 1 PN 的数量，我们记 PN ( N ) \text{PN}(N) PN ( N ) n n n PN ( N ) ∼ ζ ( 3 2 ) ζ ( 3 ) N ≈ 2.173 N \text{PN}(N) \sim \frac{\zeta(\frac{3}{2})}{\zeta(3)} \sqrt{N} \approx 2.173 \sqrt{N} PN ( N ) ∼ ζ ( 3 ) ζ ( 2 3 ) N ≈ 2.173 N PN ( N ) ≈ N log N \text{PN}(N) \approx \frac{\sqrt{N}}{\log N} PN ( N ) ≈ l o g N N
那么这玩意对我筛
f ( n ) f(n) f ( n ) 前缀和有什么用啊，其核心思路在于我们需要先找一个辅助的函数
g ( n ) g(n) g ( n ) 满足：
g ( p ) = f ( p ) g(p) = f(p) g ( p ) = f ( p ) p p p g ( n ) g(n) g ( n ) G ( n ) = ∑ i = 1 n g ( i ) G(n) = \sum_{i=1}^n g(i) G ( n ) = ∑ i = 1 n g ( i ) g g g
看到这个辅助函数，也许你就会想到卷积，确实，定义
h h h 满足：
f = g × h ⇔ f ( n ) = ∑ d ∣ n g ( d ) h ( n d ) f = g \times h \quad \Leftrightarrow \quad f(n) = \sum_{d|n} g(d) h\left(\frac{n}{d}\right) f = g × h ⇔ f ( n ) = d ∣ n ∑ g ( d ) h ( d n ) 也就是狄利克雷卷积，其中
h h h 必须为积性函数。
然后考虑从
h h h 入手，先计算
h ( p k ) h(p^k) h ( p k ) 。
在 n = p e n = p^e n = p e f ( p e ) = ∑ i = 0 e g ( p i ) h ( p e − i ) f(p^e) = \sum_{i=0}^e g(p^i) h(p^{e-i}) f ( p e ) = ∑ i = 0 e g ( p i ) h ( p e − i )
特别的。如果 e = 1 e = 1 e = 1 f ( p ) = g ( p ) h ( 1 ) + g ( 1 ) h ( p ) f(p) = g(p)h(1) + g(1)h(p) f ( p ) = g ( p ) h ( 1 ) + g ( 1 ) h ( p ) g ( p ) = g ( p ) + h ( p ) ⇒ h ( p ) = 0 g(p) = g(p) + h(p) \quad \Rightarrow \quad h(p) = 0 g ( p ) = g ( p ) + h ( p ) ⇒ h ( p ) = 0
一条关键的结论：
h ( p ) h(p) h ( p ) 为
0 0 0 对于所有素数
p p p 成立。质数部分就算完了。
然后考虑
h h h 非
0 0 0 值和 PN 的关系，由于
h h h 为积性函数且
h ( p ) = 0 h(p) = 0 h ( p ) = 0 在
p p p 为质数下。那么对于包含一次质因子的
n n n 都有
h ( n ) = 0 h(n) = 0 h ( n ) = 0 ， 这个非常好证明。
然后我们就要捣鼓前缀和了，前方高能！
由
f = g × h f = g \times h f = g × h ：
f ( n ) = ∑ d ∣ n g ( d ) h ( n d ) f(n) = \sum_{d|n} g(d) h\left(\frac{n}{d}\right) f ( n ) = d ∣ n ∑ g ( d ) h ( d n ) 带入求前缀和：
S f ( n ) = ∑ i = 1 n f ( i ) = ∑ i = 1 n ∑ d ∣ i g ( d ) h ( i d ) S_f(n) = \sum_{i=1}^n f(i) = \sum_{i=1}^n \sum_{d|i} g(d) h\left(\frac{i}{d}\right) S f ( n ) = i = 1 ∑ n f ( i ) = i = 1 ∑ n d ∣ i ∑ g ( d ) h ( d i ) 令
k = i d k = \frac{i}{d} k = d i 则
i = d k i = dk i = d k 且
d ∣ i d \mid i d ∣ i ，交换求和：
S f ( n ) = ∑ d = 1 n g ( d ) ∑ k = 1 ⌊ n d ⌋ h ( k ) S_f(n) = \sum_{d=1}^n g(d) \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} h(k) S f ( n ) = d = 1 ∑ n g ( d ) k = 1 ∑ ⌊ d n ⌋ h ( k ) 由于
h ( k ) h(k) h ( k ) 仅在
k k k 是 PN 时非 0，则我们可以尝试枚举所有可能的
k k k ，从原始的二层求和展开：
S f ( n ) = ∑ i = 1 n ∑ d ∣ i g ( d ) h ( i d ) S_f(n) = \sum_{i=1}^n \sum_{d|i} g(d) h\left(\frac{i}{d}\right) S f ( n ) = i = 1 ∑ n d ∣ i ∑ g ( d ) h ( d i ) S f ( n ) = ∑ k = 1 n h ( k ) ∑ d = 1 ⌊ n k ⌋ g ( d ) = ∑ k = 1 n h ( k ) ⋅ G ( ⌊ n k ⌋ ) S_f(n) = \sum_{k=1}^n h(k) \sum_{d=1}^{\lfloor \frac{n}{k} \rfloor} g(d)
= \sum_{k=1}^n h(k) \cdot G\left(\left\lfloor \frac{n}{k} \right\rfloor\right) S f ( n ) = k = 1 ∑ n h ( k ) d = 1 ∑ ⌊ k n ⌋ g ( d ) = k = 1 ∑ n h ( k ) ⋅ G ( ⌊ k n ⌋ ) 根据我们上面的性质有：
S f ( n ) = ∑ k = 1 k is PN n h ( k ) ⋅ G ( ⌊ n k ⌋ ) S_f(n) = \sum_{\substack{k=1 \\ k \text{ is PN}}}^n h(k) \cdot G\left(\left\lfloor \frac{n}{k} \right\rfloor\right) S f ( n ) = k = 1 k is PN ∑ n h ( k ) ⋅ G ( ⌊ k n ⌋ ) 现在开始，PN 已经被我们推导完了核心部分！
计算办法很简单，由卷积关系在
n = p e n = p^e n = p e 处：
f ( p e ) = ∑ i = 0 e g ( p i ) h ( p e − i ) f(p^e) = \sum_{i=0}^e g(p^i) h(p^{e-i}) f ( p e ) = i = 0 ∑ e g ( p i ) h ( p e − i ) f ( p e ) = g ( 1 ) h ( p e ) + ∑ i = 1 e g ( p i ) h ( p e − i ) f(p^e) = g(1)h(p^e) + \sum_{i=1}^e g(p^i) h(p^{e-i}) f ( p e ) = g ( 1 ) h ( p e ) + i = 1 ∑ e g ( p i ) h ( p e − i ) 由于
g ( 1 ) = 1 g(1) = 1 g ( 1 ) = 1 ，得：
h ( p e ) = f ( p e ) − ∑ i = 1 e g ( p i ) h ( p e − i ) h(p^e) = f(p^e) - \sum_{i=1}^e g(p^i) h(p^{e-i}) h ( p e ) = f ( p e ) − i = 1 ∑ e g ( p i ) h ( p e − i ) 所以算法的步骤就是：
找出辅助函数，满足上面要求。
筛出所有 ≤ n \le \sqrt{n} ≤ n G ( m ) G(m) G ( m ) m = ⌊ n k ⌋ m = \lfloor \frac{n}{k} \rfloor m = ⌊ k n ⌋
最后计算每一个 h h h h h h
又来到了时间复杂度分析的部分，但是由于这个过于简单，就随便写一下，你只需要知道 PN 个数是
n \sqrt{n} n 的大致就知道时间复杂度了。
References: 
Oi-Wiki (Min_25)(Powerful Number)