I'm LaTex Dalao！

黄子凯1 · 2024 年10 月 2 日 00:28

@信友队蔡老师
本算法最初由 @wangchenyi 发明，时间复杂度为
O(\dfrac{n}{\log_2n}) ，常数巨大，大约 100100100 倍常数。原帖在这，我帮他做了格式上的优化。

算法思路和时间复杂度证明

以下方便起见，令 p 为质数序列（ p_1=2, p_2=3,\dots ）， m(n) 为小于 n 的质数个数， w(n) 为小于 n 的非完全合数。

本算法主要是通过递推跳过“完全合数”。完全合数和非完全合数定义如下：对一个合数 n ，令 c = c(n) 为最大的整数使 \prod\limits_{i=1}^cp_i<n ，若存在 k(1\le k\le c) ，使 p_k\mid n ，则称 n 为完全合数，否则为不完全合数。

由代码中的递推找到所有质数和非完全合数只需 O(m + w) （请注意 \displaystyle \sum\limits_{k=1}^\infty\prod\limits_{i=1}^k\dfrac{1}{p_i}<\sum\limits_{k=1}^\infty\dfrac{1}{k(k-1)}=2 ）。而之后我们可以通过 O(w) 的时间复杂度来找到所有非完全合数，再用 O(\sqrt{n}+w) 的时间复杂度来排序，然后是 O(m + w) 的输出。

现在此算法时间复杂度为 O(m + w + \sqrt{n}) = O(\dfrac{n}{\log_2n} = O(m)) ，故时间复杂度为 O(m + w) 。

下证： \lim\limits_{n\to\infty}m+w=\dfrac{n}{\log_2n} 。

（以下等于号 = 按等价理解）
由定义， \displaystyle m + w = n \times \prod\limits_{i=1}^m(1-\dfrac{1}{p_i}) 。

令 \displaystyle T = T(n) = \prod\limits_{i=1}^m(1-\dfrac{1}{p_i}) ，我们证明 T < \dfrac{e^2}{\log_2n}:\log_2T = \displaystyle \sum\limits_{i=1}^m\log_2(1-dfrac{1}{p_i}) ，由
\log_2(1-x) 的解析性，知它的泰勒级数收敛于它本身，故：

\begin{aligned}\log_2T&=\sum\limits_{i=1}^m\sum\limits_{k=1}^\infty\dfrac{1}{kp_i^k}\ &=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k} \end{aligned}

我们估计 \displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i^k}m∑i=11pki\displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i^k} 的量级，显然，对于任意的 k\ge2 ，

\begin{aligned} \sum\limits_{i=1}^m&\le\sum\limits_{i=2}^{m+1}\dfrac{1}{i}\ &<\int_1^{m+1}\dfrac{1}{x^k}\mathrm dx\ &=\dfrac{1}{k-1}(1-\dfrac{1}{(m+1)^{k-1}})\ &<\dfrac{1}{k-1} \end{aligned}

故

\begin{aligned}\log_2T&=\sum\limits_{i=1}^m\sum\limits_{k=1}^\infty\dfrac{1}{kp_i^k}\ &=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}\ &<\sum\limits_{i=1}^m\dfrac{1}{p_i}+1 \end{aligned}

即

\begin{aligned}\log_2T&=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}\ &=\sum\limits_{i=1}^m\dfrac{1}{p_i^k}+\theta_n(0<\theta_n<1) \end{aligned}

我们只需估计 \displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i} ，由熟知结论， \displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i}>\log_2\log_2n-1 ，故 \log_2T<\log_2\log_2n+2 ，即 T<\dfrac{e^2}{\log_2n} ，故 O(m + w) = O(Tn) = O(\dfrac{n}{\log_2n}) ，我们证明了此算法的时间复杂度绝不可能改进，后人只能优化常数（是的，常数非常大），证毕。

黄子凯1 · 2024 年10 月 2 日 00:30

草，$\LaTeX$ 炸了！破信友队！

黄景轩 · 2024 年10 月 2 日 02:03

\LaTeX

黄景轩 · 2024 年10 月 2 日 02:04

可以用啊，你试试用空格与其他非LaTeX字符分隔一下

黄景轩 · 2024 年10 月 2 日 02:05

123$\LaTeX$
123 \LaTeX

汪嘉乐 · 2024 年10 月 3 日 03:47

@信友队蔡老师
本算法最初由 @wangchenyi 发明，时间复杂度为
O(\dfrac{n}{\log_2n}) ，常数巨大，大约 100100100 倍常数。原帖在这，我帮他做了格式上的优化。

算法思路和时间复杂度证明

以下方便起见，令 p 为质数序列（ p_1=2, p_2=3,\dots ）， m(n) 为小于 n 的质数个数， w(n) 为小于 n 的非完全合数。

本算法主要是通过递推跳过“完全合数”。完全合数和非完全合数定义如下：对一个合数 n ，令 c = c(n) 为最大的整数使 \prod\limits_{i=1}^cp_i<n ，若存在 k(1\le k\le c) ，使 p_k\mid n ，则称 n 为完全合数，否则为不完全合数。

由代码中的递推找到所有质数和非完全合数只需 O(m + w) （请注意 \displaystyle \sum\limits_{k=1}^\infty\prod\limits_{i=1}^k\dfrac{1}{p_i}<\sum\limits_{k=1}^\infty\dfrac{1}{k(k-1)}=2 ）。而之后我们可以通过 O(w) 的时间复杂度来找到所有非完全合数，再用 O(\sqrt{n}+w) 的时间复杂度来排序，然后是 O(m + w) 的输出。

现在此算法时间复杂度为 O(m + w + \sqrt{n}) = O(\dfrac{n}{\log_2n} = O(m)) ，故时间复杂度为 O(m + w) 。

下证： \lim\limits_{n\to\infty}m+w=\dfrac{n}{\log_2n} 。

（以下等于号 = 按等价理解）
由定义， \displaystyle m + w = n \times \prod\limits_{i=1}^m(1-\dfrac{1}{p_i}) 。

令 \displaystyle T = T(n) = \prod\limits_{i=1}^m(1-\dfrac{1}{p_i}) ，我们证明 T < \dfrac{e^2}{\log_2n}:\log_2T = \displaystyle \sum\limits_{i=1}^m\log_2(1-dfrac{1}{p_i}) ，由
\log_2(1-x) 的解析性，知它的泰勒级数收敛于它本身，故：

\begin{aligned}\log_2T&=\sum\limits_{i=1}^m\sum\limits_{k=1}^\infty\dfrac{1}{kp_i^k}\ &=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k} \end{aligned}

我们估计 \displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i^k}m∑i=11pki\displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i^k} 的量级，显然，对于任意的 k\ge2 ，

\begin{aligned} \sum\limits_{i=1}^m&\le\sum\limits_{i=2}^{m+1}\dfrac{1}{i}\ &<\int_1^{m+1}\dfrac{1}{x^k}\mathrm dx\ &=\dfrac{1}{k-1}(1-\dfrac{1}{(m+1)^{k-1}})\ &<\dfrac{1}{k-1} \end{aligned}

故

\begin{aligned}\log_2T&=\sum\limits_{i=1}^m\sum\limits_{k=1}^\infty\dfrac{1}{kp_i^k}\ &=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}\ &<\sum\limits_{i=1}^m\dfrac{1}{p_i}+1 \end{aligned}

即

\begin{aligned}\log_2T&=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}\ &=\sum\limits_{i=1}^m\dfrac{1}{p_i^k}+\theta_n(0<\theta_n<1) \end{aligned}

我们只需估计 \displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i} ，由熟知结论， \displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i}>\log_2\log_2n-1 ，故 \log_2T<\log_2\log_2n+2 ，即 T<\dfrac{e^2}{\log_2n} ，故 O(m + w) = O(Tn) = O(\dfrac{n}{\log_2n}) ，我们证明了此算法的时间复杂度绝不可能改进，后人只能优化常数（是的，常数非常大），证毕。

©黄子凯

由汪嘉乐修整

汪嘉乐 · 2024 年10 月 3 日 03:49

@黄子凯1 怎么样？
Am I LaTex Dalao?

邬承洛 · 2024 年10 月 3 日 14:31

\LaTeX

jhxs988 · 2024 年10 月 3 日 15:27

本算法最初由 @wangchenyi 发明，时间复杂度为 O(\dfrac{n}{\log_2n}) ，常数巨大，大约 100 倍常数。原帖在这，我帮他做了格式上的优化。

算法思路和时间复杂度证明

以下方便起见，令 p 为质数序列（ p_1=2, p_2=3,\dots ）， m(n) 为小于 n 的质数个数， w(n) 为小于 n 的非完全合数。

本算法主要是通过递推跳过“完全合数”。完全合数和非完全合数定义如下：对一个合数 n ，令
c=c(n) 为最大的整数使 \prod\limits_{i=1}^cp_i<n ，若存在 k(1\le k\le c) ，使 p_k\mid n ，则称 n 为完全合数，否则为不完全合数。

由代码中的递推找到所有质数和非完全合数只需 O(m + w) （请注意 \displaystyle\sum\limits_{k=1}^\infty\prod\limits_{i=1}^k\dfrac{1}{p_i}<\sum\limits_{k=1}^\infty\dfrac{1}{k(k-1)}=2 )。而之后我们可以通过 O(w) 的时间复杂度来找到所有非完全合数，再用 O(\sqrt{n}+w) 的时间复杂度来排序，然后是 O(m+w) 的输出。

现在此算法时间复杂度为 O(m + w + \sqrt{n}) = O(\dfrac{n}{\log_2n} = O(m)) ，故时间复杂度为 O(m + w) 。

下证： \lim\limits_{n\to\infty}m+w=\dfrac{n}{\log_2n} 。

（以下等于号 = 按等价理解）
由定义， \displaystyle m + w = n \times \prod\limits_{i=1}^m(1-\dfrac{1}{p_i}) 。

令 \displaystyle T = T(n) = \prod\limits_{i=1}^m(1-\dfrac{1}{p_i}) ，我们证明 T < \dfrac{e^2}{\log_2n} ： \log_2T = \displaystyle \sum\limits_{i=1}^m\log_2(1-dfrac{1}{p_i}) ，由 \log_2(1-x) 的解析性，知它的泰勒级数收敛于它本身，故：

\begin{aligned}\log_2T&=\sum\limits_{i=1}^m\sum\limits_{k=1}^\infty\dfrac{1}{kp_i^k}\ &=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k} \end{aligned}

我们估计 \begin{align} \sum_{i=1}^{m} \frac{1}{p^{k}_{i}} \end{align} 的量级，显然，对于任意的 k \ge 2 ，
\begin{aligned} \sum\limits_{i=1}^m&\le\sum\limits_{i=2}^{m+1}\dfrac{1}{i}\ &<\int_1^{m+1}\dfrac{1}{x^k}\mathrm dx\ &=\dfrac{1}{k-1}(1-\dfrac{1}{(m+1)^{k-1}})\ &<\dfrac{1}{k-1} \end{aligned}

故

\begin{aligned}\log_2T&=\sum\limits_{i=1}^m\sum\limits_{k=1}^\infty\dfrac{1}{kp_i^k}\ &=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}\ &<\sum\limits_{i=1}^m\dfrac{1}{p_i}+1 \end{aligned}

即

\begin{aligned}\log_2T&=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}\ &=\sum\limits_{i=1}^m\dfrac{1}{p_i^k}+\theta_n(0<\theta_n<1) \end{aligned}

我们只需估计 \displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i} ，由熟知结论， \displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i}>\log_2\log_2n-1 ，故
\log_2T<\log_2\log_2n+2 ，即 T<\dfrac{e^2}{\log_2n} ，故 O(m + w) = O(Tn) = O(\dfrac{n}{\log_2n}) ，我们证明了此算法的时间复杂度绝不可能改进，后人只能优化常数（是的，常数非常大），证毕。

© @黄子凯1

由 @jhxs988 修正

黄子凯1 · 2024 年10 月 4 日 06:46

源码给我啊啊啊啊

汪嘉乐 · 2024 年10 月 6 日 06:47

@信友队蔡老师
本算法最初由 @[wangchenyi ](https://www.luogu.com/user/631814) 发明，时间复杂度为 
 $O(\dfrac{n}{\log_2n})$ ，常数巨大，大约 100100100 倍常数。[原帖在这 ](https://www.luogu.com/discuss/839771)，我帮他做了格式上的优化。

## 算法思路和时间复杂度证明

以下方便起见，令 $p$ 为质数序列（ $p_1=2, p_2=3,\dots$ ）， $m(n)$ 为小于 $n$ 的质数个数， $w(n)$  为小于 $n$ 的非完全合数。

本算法主要是通过递推跳过“完全合数”。完全合数和非完全合数定义如下： 对一个合数  $n$ ，令 $c = c(n)$ 为最大的整数使 $\prod\limits_{i=1}^cp_i<n$ ，若存在  $k(1\le k\le c)$ ，使 $p_k\mid n$ ，则称 $n$ 为完全合数，否则为不完全合数。

由代码中的递推找到所有质数和非完全合数只需 $O(m + w) $ （请注意 $ \displaystyle \sum\limits_{k=1}^\infty\prod\limits_{i=1}^k\dfrac{1}{p_i}<\sum\limits_{k=1}^\infty\dfrac{1}{k(k-1)}=2$ ）。而之后我们可以通过 $O(w)$ 的时间复杂度来找到所有非完全合数，再用 $O(\sqrt{n}+w)$ 的时间复杂度来排序，然后是 $O(m + w)$ 的输出。

现在此算法时间复杂度为 $O(m + w + \sqrt{n}) = O(\dfrac{n}{\log_2n} = O(m))$ ，故时间复杂度为 $O(m + w)$ 。

下证： $\lim\limits_{n\to\infty}m+w=\dfrac{n}{\log_2n}$ 。

（以下等于号 = 按等价理解）
由定义， $\displaystyle m + w = n \times \prod\limits_{i=1}^m(1-\dfrac{1}{p_i})$ 。

令 $\displaystyle T = T(n) = \prod\limits_{i=1}^m(1-\dfrac{1}{p_i})$ ，我们证明 $T < \dfrac{e^2}{\log_2n}:\log_2T = \displaystyle \sum\limits_{i=1}^m\log_2(1-dfrac{1}{p_i})$ ，由 
 $\log_2(1-x)$ 的解析性，知它的泰勒级数收敛于它本身，故：
$$
\begin{aligned}\log_2T&=\sum\limits_{i=1}^m\sum\limits_{k=1}^\infty\dfrac{1}{kp_i^k}\
&=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}
\end{aligned}
$$

我们估计 $\displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i^k}m∑i=11pki\displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i^k}$ 的量级，显然，对于任意的 $k\ge2$ ，
$$
\begin{aligned}
\sum\limits_{i=1}^m&\le\sum\limits_{i=2}^{m+1}\dfrac{1}{i}\
&<\int_1^{m+1}\dfrac{1}{x^k}\mathrm dx\
&=\dfrac{1}{k-1}(1-\dfrac{1}{(m+1)^{k-1}})\
&<\dfrac{1}{k-1}
\end{aligned}
$$

故

$$
\begin{aligned}\log_2T&=\sum\limits_{i=1}^m\sum\limits_{k=1}^\infty\dfrac{1}{kp_i^k}\
&=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}\
&<\sum\limits_{i=1}^m\dfrac{1}{p_i}+1
\end{aligned}
$$

即

$$
\begin{aligned}\log_2T&=\sum\limits_{k=1}^\infty\dfrac{1}{k}\sum\limits_{i=1}^m\dfrac{1}{p_i^k}\
&=\sum\limits_{i=1}^m\dfrac{1}{p_i^k}+\theta_n(0<\theta_n<1)
\end{aligned}
$$

我们只需估计 $\displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i}$ ，由熟知结论， $\displaystyle \sum\limits_{i=1}^m\dfrac{1}{p_i}>\log_2\log_2n-1$ ，故 $\log_2T<\log_2\log_2n+2$ ，即 $T<\dfrac{e^2}{\log_2n}$ ，故 $O(m + w) = O(Tn) = O(\dfrac{n}{\log_2n})$ ，我们证明了此算法的时间复杂度绝不可能改进，后人只能优化常数（是的，常数非常大），证毕。

2345安全卫士 · 2024 年11 月 14 日 12:05

警告一次（好像已经警告过了）

2345安全卫士 · 2024 年11 月 14 日 12:07

2345安全卫士 · 2024 年11 月 14 日 12:07

那就直接封禁