为什么埃式筛法的时间复杂度是O(nloglogn)？
好的，咱们来聊聊埃氏筛法为啥效率这么高，能达到 $O(n log log n)$ 这个让人觉得有点炫酷的复杂度。这事儿得从头说起，一点一点拆解。
什么是埃氏筛法？
首先，你得明白埃氏筛法是干嘛的。它的主要目标是从 1 到 n 这样一个区间里，把所有的质数都找出来。它不像咱们一个个数去试能不能被整除那么费劲，而是采取一种“筛”的方式，一遍遍地划掉合数。
基本思路
1. 一个数组，从 2 开始，把所有数都当成可能是质数。
2. 找到第一个未被划掉的数，比如 2。这个数就是质数。
3. 然后，把这个质数的所有倍数（4, 6, 8, 10...）都划掉，因为它们肯定是合数。
4. 继续往下找，找到下一个未被划掉的数，比如 3。这个数也是质数。
5. 再把 3 的所有倍数（6, 9, 12, 15...）划掉。注意，有些已经被划掉了（比如 6），没关系，重复划也无妨。
6. 重复这个过程，直到你处理到根号 n 就可以了。为啥是根号 n 呢？因为如果一个数 N 是合数，它肯定有一个小于等于根号 N 的因子。如果它比根号 N 都要大，那它另一个因子就必然小于根号 N 了，那个小因子早就已经把 N 划掉了。
为什么不是 $O(n^2)$ 或者 $O(n log n)$？
你想想，如果咱们真的去对每一个数进行试除，比如检查 1 到 n 的每一个数是否能被比它小的数整除，那复杂度会很高。
一个朴素的方法是，对于每个数 i 从 2 到 n，再去检查从 2 到 i1 的每个数 j，看看 i 是否能被 j 整除。这样的话，每个数都可能需要做 O(i) 次判断，总共就是 O(n^2) 的复杂度了，效率很低。
稍微好一点，我们知道只需要检查到 $sqrt{i}$ 就可以了，这样对于每个数 i，需要 O($sqrt{i}$) 的操作。对所有数求和下来，复杂度大约是 $O(n sqrt{n})$。
更进一步，如果咱们只用质数去除，也就是我们说的埃氏筛法的“筛”的逻辑，那复杂度会进一步降低。
揭秘 $O(n log log n)$
现在咱们重点来看看埃氏筛法是如何做到 $O(n log log n)$ 的。这涉及到两个关键的部分：
1. 筛掉倍数的操作总次数。
2. 质数分布的规律。
咱们一步步来分析：
第一步：计算筛掉倍数的操作总次数
想象一下，我们从 2 开始，把 2 的倍数都划掉：$2 imes 2, 2 imes 3, 2 imes 4, dots, 2 imes (n/2)$。 大概是 $n/2$ 个数。
然后是 3，把 3 的倍数划掉：$3 imes 2$ (已经划了), $3 imes 3, 3 imes 4, dots, 3 imes (n/3)$。 大概是 $n/3$ 个数。
接着是 5，把 5 的倍数划掉：$5 imes 2$ (已经划了), $5 imes 3$ (已经划了), $dots, 5 imes k$, 直到 $5k le n$。 大概是 $n/5$ 个数。
依此类推，对于每一个质数 $p le n$，我们都会去划掉它的倍数，也就是 $p imes 2, p imes 3, p imes 4, dots$ 直到 $p imes k le n$。 这意味着我们对 $p$ 的倍数进行了 $n/p 1$ 次操作（因为 $p imes 1 = p$ 本身是质数，不用划）。
所以，我们总共要做的“划掉倍数”的操作次数，大致可以写成这样一个求和：
$S = frac{n}{2} + frac{n}{3} + frac{n}{5} + frac{n}{7} + dots$ (这里只列出了质数作为筛子的基数)
我们把这个式子写成更数学一点的形式：
$S approx n left( frac{1}{2} + frac{1}{3} + frac{1}{5} + frac{1}{7} + dots + frac{1}{p} ight)$，其中 $p le n$ 且 $p$ 是质数。
第二步：质数分布的规律和调和级数
现在关键来了：那个 $left( frac{1}{2} + frac{1}{3} + frac{1}{5} + frac{1}{7} + dots + frac{1}{p} ight)$ 这部分是怎么算的？
这里涉及到 素数定理 的一个推论，以及 调和级数 的概念。
调和级数：咱们都知道，级数 $1 + frac{1}{2} + frac{1}{3} + frac{1}{4} + dots$ 是发散的，它的部分和大约是 $ln n$。 具体来说，$sum_{i=1}^n frac{1}{i} approx ln n$。
质数的倒数和：欧拉证明过，所有质数的倒数和也是发散的，而且它的增长速度和调和级数非常相似。 具体来说，所有小于等于 n 的质数的倒数和：
$sum_{p le n, p ext{ is prime}} frac{1}{p} approx ln(ln n)$
这个 $ln(ln n)$ 是一个增长非常缓慢的函数。 你可以理解为：
n 增大 10 倍， $ln n$ 增长的量是 $ln 10$。
n 增大 10 倍， $ln(ln n)$ 增长的量是 $ln(ln(10n)) ln(ln n) = ln(frac{ln(10n)}{ln n}) = ln(1 + frac{ln 10}{ln n})$，这个量非常小。
把它们结合起来
回到我们之前计算的操作总次数：
$S approx n left( frac{1}{2} + frac{1}{3} + frac{1}{5} + frac{1}{7} + dots + frac{1}{p} ight)$
我们知道前面那个括号里的和是 $ln(ln n)$ 的量级。 所以，总的操作次数就是 $n imes ln(ln n)$ 的量级。
为什么是 $O(n log log n)$ 而不是精确的 $n ln ln n$?
在算法分析里，我们通常用大 O 记号来表示一个算法渐进的增长趋势，忽略常数因子和低阶项。 $O(n log log n)$ 就抓住了这个核心的增长速度。
另外，还有一个小细节：埃氏筛法会重复筛。比如 6 被 2 筛了，也被 3 筛了。 但是，这并不影响最终的复杂度分析，因为即使是重复筛，我们本质上还是在遍历那些合数。关键在于，我们是遍历 质数 的倍数来做筛除，而不是遍历 所有数 去判断是否是质数。 遍历质数这个过程本身，质数在数轴上的分布就决定了后面那一项 $log log n$ 的出现。
总结一下
埃氏筛法的 $O(n log log n)$ 复杂度，可以理解为：
1. 我们对每一个小于等于 $n$ 的质数 $p$，执行一次筛除操作。这个操作涉及划掉 $p$ 的倍数，大概耗费 $n/p$ 的工作量。
2. 所有质数倒数和 $sum_{p le n} frac{1}{p}$ 的增长趋势是 $log log n$。
3. 所以，总的操作次数就是 $n imes (sum frac{1}{p}) approx n log log n$。
这个复杂度比我们之前提到的任何方法都要好，因为它有效地利用了质数的分布规律，并且避免了不必要的重复判断。 整个过程就像是在对一个大池塘里的鱼进行筛选，你不是一条条去抓，而是找出那些会产卵的母鱼，然后把它们的水域标记出来，间接地就把很多小鱼（合数）给解决了。 效率自然就高了。
什么是埃氏筛法？
首先，你得明白埃氏筛法是干嘛的。它的主要目标是从 1 到 n 这样一个区间里，把所有的质数都找出来。它不像咱们一个个数去试能不能被整除那么费劲，而是采取一种“筛”的方式，一遍遍地划掉合数。
基本思路
1. 一个数组，从 2 开始，把所有数都当成可能是质数。
2. 找到第一个未被划掉的数，比如 2。这个数就是质数。
3. 然后，把这个质数的所有倍数（4, 6, 8, 10...）都划掉，因为它们肯定是合数。
4. 继续往下找，找到下一个未被划掉的数，比如 3。这个数也是质数。
5. 再把 3 的所有倍数（6, 9, 12, 15...）划掉。注意，有些已经被划掉了（比如 6），没关系，重复划也无妨。
6. 重复这个过程，直到你处理到根号 n 就可以了。为啥是根号 n 呢？因为如果一个数 N 是合数，它肯定有一个小于等于根号 N 的因子。如果它比根号 N 都要大，那它另一个因子就必然小于根号 N 了，那个小因子早就已经把 N 划掉了。
为什么不是 $O(n^2)$ 或者 $O(n log n)$？
你想想，如果咱们真的去对每一个数进行试除，比如检查 1 到 n 的每一个数是否能被比它小的数整除，那复杂度会很高。
一个朴素的方法是，对于每个数 i 从 2 到 n，再去检查从 2 到 i1 的每个数 j，看看 i 是否能被 j 整除。这样的话，每个数都可能需要做 O(i) 次判断，总共就是 O(n^2) 的复杂度了，效率很低。
稍微好一点，我们知道只需要检查到 $sqrt{i}$ 就可以了，这样对于每个数 i，需要 O($sqrt{i}$) 的操作。对所有数求和下来，复杂度大约是 $O(n sqrt{n})$。
更进一步，如果咱们只用质数去除，也就是我们说的埃氏筛法的“筛”的逻辑，那复杂度会进一步降低。
揭秘 $O(n log log n)$
现在咱们重点来看看埃氏筛法是如何做到 $O(n log log n)$ 的。这涉及到两个关键的部分：
1. 筛掉倍数的操作总次数。
2. 质数分布的规律。
咱们一步步来分析：
第一步：计算筛掉倍数的操作总次数
想象一下，我们从 2 开始，把 2 的倍数都划掉：$2 imes 2, 2 imes 3, 2 imes 4, dots, 2 imes (n/2)$。 大概是 $n/2$ 个数。
然后是 3，把 3 的倍数划掉：$3 imes 2$ (已经划了), $3 imes 3, 3 imes 4, dots, 3 imes (n/3)$。 大概是 $n/3$ 个数。
接着是 5，把 5 的倍数划掉：$5 imes 2$ (已经划了), $5 imes 3$ (已经划了), $dots, 5 imes k$, 直到 $5k le n$。 大概是 $n/5$ 个数。
依此类推，对于每一个质数 $p le n$，我们都会去划掉它的倍数，也就是 $p imes 2, p imes 3, p imes 4, dots$ 直到 $p imes k le n$。 这意味着我们对 $p$ 的倍数进行了 $n/p 1$ 次操作（因为 $p imes 1 = p$ 本身是质数，不用划）。
所以，我们总共要做的“划掉倍数”的操作次数，大致可以写成这样一个求和：
$S = frac{n}{2} + frac{n}{3} + frac{n}{5} + frac{n}{7} + dots$ (这里只列出了质数作为筛子的基数)
我们把这个式子写成更数学一点的形式：
$S approx n left( frac{1}{2} + frac{1}{3} + frac{1}{5} + frac{1}{7} + dots + frac{1}{p} ight)$，其中 $p le n$ 且 $p$ 是质数。
第二步：质数分布的规律和调和级数
现在关键来了：那个 $left( frac{1}{2} + frac{1}{3} + frac{1}{5} + frac{1}{7} + dots + frac{1}{p} ight)$ 这部分是怎么算的？
这里涉及到 素数定理 的一个推论，以及 调和级数 的概念。
调和级数：咱们都知道，级数 $1 + frac{1}{2} + frac{1}{3} + frac{1}{4} + dots$ 是发散的，它的部分和大约是 $ln n$。 具体来说，$sum_{i=1}^n frac{1}{i} approx ln n$。
质数的倒数和：欧拉证明过，所有质数的倒数和也是发散的，而且它的增长速度和调和级数非常相似。 具体来说，所有小于等于 n 的质数的倒数和：
$sum_{p le n, p ext{ is prime}} frac{1}{p} approx ln(ln n)$
这个 $ln(ln n)$ 是一个增长非常缓慢的函数。 你可以理解为：
n 增大 10 倍， $ln n$ 增长的量是 $ln 10$。
n 增大 10 倍， $ln(ln n)$ 增长的量是 $ln(ln(10n)) ln(ln n) = ln(frac{ln(10n)}{ln n}) = ln(1 + frac{ln 10}{ln n})$，这个量非常小。
把它们结合起来
回到我们之前计算的操作总次数：
$S approx n left( frac{1}{2} + frac{1}{3} + frac{1}{5} + frac{1}{7} + dots + frac{1}{p} ight)$
我们知道前面那个括号里的和是 $ln(ln n)$ 的量级。 所以，总的操作次数就是 $n imes ln(ln n)$ 的量级。
为什么是 $O(n log log n)$ 而不是精确的 $n ln ln n$?
在算法分析里，我们通常用大 O 记号来表示一个算法渐进的增长趋势，忽略常数因子和低阶项。 $O(n log log n)$ 就抓住了这个核心的增长速度。
另外，还有一个小细节：埃氏筛法会重复筛。比如 6 被 2 筛了，也被 3 筛了。 但是，这并不影响最终的复杂度分析，因为即使是重复筛，我们本质上还是在遍历那些合数。关键在于，我们是遍历 质数 的倍数来做筛除，而不是遍历 所有数 去判断是否是质数。 遍历质数这个过程本身，质数在数轴上的分布就决定了后面那一项 $log log n$ 的出现。
总结一下
埃氏筛法的 $O(n log log n)$ 复杂度，可以理解为：
1. 我们对每一个小于等于 $n$ 的质数 $p$，执行一次筛除操作。这个操作涉及划掉 $p$ 的倍数，大概耗费 $n/p$ 的工作量。
2. 所有质数倒数和 $sum_{p le n} frac{1}{p}$ 的增长趋势是 $log log n$。
3. 所以，总的操作次数就是 $n imes (sum frac{1}{p}) approx n log log n$。
这个复杂度比我们之前提到的任何方法都要好，因为它有效地利用了质数的分布规律，并且避免了不必要的重复判断。 整个过程就像是在对一个大池塘里的鱼进行筛选，你不是一条条去抓，而是找出那些会产卵的母鱼，然后把它们的水域标记出来，间接地就把很多小鱼（合数）给解决了。 效率自然就高了。
网友意见
以下均表示所有小于等于的质数。
for(int i=2;i<=n;i++) if(prime[i]) for(int j=2;j*i<=n;j++) prime[i*j]=false; 以这段代码为例，时间复杂度显然为
根据Mertens' theorems，，，所以上述算法的时间复杂度为。
证明在此，我是一个搬运工，http://arxiv.org/pdf/math/0504289。（看了半天没看懂捂脸逃……
类似的话题
-
好的，咱们来聊聊埃氏筛法为啥效率这么高，能达到 $O(n log log n)$ 这个让人觉得有点炫酷的复杂度。这事儿得从头说起，一点一点拆解。什么是埃氏筛法？首先，你得明白埃氏筛法是干嘛的。它的主要目标是从 1 到 n 这样一个区间里，把所有的质数都找出来。它不像咱们一个个数去试能不能被整除那么费............. -
这个问题问得相当好，也很核心！埃氏筛法之所以只筛到根号 n，是因为它背后的数学原理，而且理解了这一点，你会发现这个算法的设计非常巧妙。我们来一点点拆解它，就像剥洋葱一样，一层一层地看清楚。 什么是埃氏筛法？首先，快速回顾一下埃氏筛法的基本操作：1. 从 2 开始，将所有 2 的倍数标记为合数。2..............
-
式姐对黑桐干也的情感，绝不是那种一见钟情、轰轰烈烈爱得死去活活的典型爱情故事。她的喜欢，是掺杂了太多复杂的情感，是历经风雨后的某种必然，是两颗孤独灵魂深处最细微的契合。要说清楚，得一点点掰开了讲。首先，得从式姐的特质说起。她是个“两仪式”，拥有名为“直死之魔眼”的能力，能看到万物背后的“死线”和“点.............
-
说虎式坦克“战斗力并不强”的说法，其实有点过于片面，甚至可以说是一种误读。恰恰相反，在它所处的那个年代，虎式坦克的战斗力是毋庸置疑的顶尖水平，甚至可以说是重新定义了重型坦克的标杆。之所以很多人“追捧吹上天”，并不是因为它不强，而是因为它太强了，强到超出了那个时代大部分武器装备的应对能力，从而在战场上.............
-
好，咱们来聊聊这二战后，交错式负重轮怎么就销声匿迹了。你可能见过一些老照片，或者玩过一些早期坦克游戏，里面那些坦克履带下面，一排排的轮子排列得挺有意思，有的挨得近，有的离得远，这就是所谓的“交错式负重轮”，也叫“ হ্রাস 轮”或者“悬挂式负重轮”。它在二战时可是不少德系坦克的标志性配置，比如虎式.............
-
意式冰淇淋（gelato）在中国市场的接受度，相比其在全球其他地方的受欢迎程度，确实显得有些“水土不服”。这背后的原因复杂且多维，并非简单的口味偏好就能解释。我们可以从几个关键方面来剖析：1. 消费习惯的差异：文化与饮食的根基 对“冰”的认知与期望： 在很多西方国家，冰淇淋（包括gelato）是.............
-
话说咱中国陆军的99式主战坦克，那可真是咱们的“陆地骄子”，威风凛凛。你可能注意到，跟早期的一些坦克不一样，99式装备的炮塔，造型上跟以前的“半蛋形”有些区别，变得更棱角分明了。这可不是随随便便改的，里面大有讲究。那咱就得先说说，到底什么是“半蛋形炮塔”？你可以想象一下，早期的一些坦克炮塔，尤其是苏.............
-
95式步枪在设计时，确实没有采用从握把下方下抛弹壳的方案，这其中有多方面的原因，需要从设计理念、人机工程、结构复杂性以及实战需求等多个角度来剖析。首先，我们得明白，弹壳抛出方向的设计，本质上是为了确保射击的连续性和射手的舒适度与安全性。传统的侧抛弹壳，无论是左抛还是右抛，都是基于绝大多数人是右撇子的.............
-
.......
-
藏獒价格的断崖式下跌是一个复杂的现象，背后有多重因素交织作用，并非单一原因能够解释。同时，关于“端上餐桌”的说法，虽然有零星的传闻，但并非普遍现象，需要审慎看待。以下是藏獒价格“断崖式下跌”的详细分析以及对“端上餐桌”传闻的探讨： 藏獒价格断崖式下跌的原因分析：1. 炒作泡沫的破裂与回归理性： .............
-
坦克底盘的研发，用“艰巨”二字来形容一点也不为过。它是一个集成了力学、材料学、热力学、工程学、甚至一定程度的空气动力学等多学科知识的复杂系统工程。想要把一个沉重的钢铁巨兽，在复杂多变的地形上，以高速、稳定的状态机动，绝非易事。首先，从基础理论和设计上讲： 承载能力与强度： 坦克的重量动辄几十吨，.............
-
前扣式文胸，听起来是不是挺方便的？一拉一扣，搞定！但为什么这么多年过去了，它们似乎总是在文胸界里扮演着一个“非主流”的角色？深入聊聊，你会发现这背后可不是简单的喜好问题，而是有一堆硬核的缺点在作祟。首先，最直观也最容易让人诟病的一点，就是支撑力普遍不足。你有没有想过，为什么我们常见的后扣式文胸，肩带.............
-
关于无托式步枪是否“正在被逐渐抛弃”这一点，其实更准确地说，是一种“高原期或冷却期，而非彻底的消亡”。无托式设计有着其独特的优势，但同时也伴随着一些难以忽视的妥协，这些因素共同作用，使得它在众多步枪设计中并未能成为主流，并且近年来似乎进入了一个相对平缓的发展阶段。要理解这一点，我们需要深入剖析无托式.............
-
说起解放军装备过的坦克，80式和59式绝对是绕不开的两款代表。但奇怪的是，不少型号的80式坦克，本应是比59式更晚 나온的“后生”，却比老迈的59式坦克还要早退役。这事儿说起来，原因可不止一星半点，得从它们的出身、设计理念、战斗力以及整个陆军装备更新换代的逻辑说起。1. 59式：历史的见证，也是历史.............
-
这个问题挺有意思的，也触及了社会文化变迁中一个很重要的现象。与其说是“消费主义式田园女权”减少了，不如说这种表现形式可能在一定程度上被更激进的言论所掩盖或挤压了空间。而“仇男恨男式极端女拳”的大量涌现，背后则牵扯着一系列复杂的社会心理和文化因素。咱们来好好掰扯掰扯。首先，得先理解一下“消费主义式田园.............
-
你这个问题问得特别有意思，聊到客机设计，这飞翼式外形绝对是个绕不开的话题，也是很多科幻爱好者心中的“完美形态”。不过，现实中的大型客机，尤其是我们天天坐的那种，为啥不像电影里那样长着一对巨大的翅膀呢？这背后其实是一系列非常现实、也非常纠结的技术和经济考量。首先，我们得搞清楚什么是飞翼式气动外形。简单.............
-
.......
-
.......
-
.......
-
.......
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有