为什么埃式筛法的时间复杂度是O(nloglogn)？ 第1页
1
zhou-xing-yu-76 网友的相关建议:
以下均表示所有小于等于的质数。
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。（看了半天没看懂捂脸逃……
1
相关话题
如何看待谭泽睿的《在平移素数数列中的无平方因子数》？一个正常智商的人终其一生能够理解费马大定理的证明吗？
如何看待这位知友提出的这个声称只有他能解的问题？
如何证明 1²+2²+…+n² 为平方数的解只有 n＝1 或 n＝24？
「应试教育」抑制了学生的创造力与想象力吗？是如何做到的？
如何评价中科大实现了媲美人脑能效的类脑突触原型器件？
物理专业学生应该具备哪些数学素养？
为什么连离我很远很远的服务器会很慢？
算法岗位真的需要顶会才能入场吗？
无限光滑的表面、有限编码的符串，哪一个才更能准确地代表我们在现实中所遇上的真实情况？
前一个讨论
为什么癌症病人眼中会产生切伦科夫光？
下一个讨论
最难的数学有多难？
相关的话题
黑客有可能攻击已经关机的电脑吗（有电源，网线连着）？这样的广义斐波那契数列能得到如下的单调性结果吗？
用数据线连接手机和电脑后，可以在手机上访问电脑硬盘中的文件吗?
威尔逊定理中 p=4是一个例外，为什么？是否存在其他非质数的例外？
计科学生能成为b站稚晖君这样软硬兼通能diy电子产品的人吗？
哪些开发会用到微积分、离散数学、线性代数、概率论的知识？
请问费马大定理写成方程形式是否可以证明？
前n项n的阶乘的和是多少1！+2！+ … +n！=？
如何看待 arXiv2111.02792 对黎曼猜想的证明？
学习机器学习应该看哪些书籍？
知乎上有哪些著名的“计算机科学”领域的“民科”？
TCP 为什么是三次握手，而不是两次或四次？
为何一个byte有8bit而不是7/9/4/16bit ?
C语言 乘以0.01快？还是除以100快？
如何评价知乎用户@逍遥自在？
推荐算法岗是否存在严重人才过剩?
求使 y=sqrt(x+a)+sqrt(x+b) 成立的正整数对 (x,y) 的数量这一类的题如何解？
计算机科学领域有什么笑话？
如何快速判断一个数可被 7 整除？
为什么很多计算机系的学生一点不会电脑的基本操作？
如何看待 HTTP/3 ？
目前 x³＋y³＋z³＝42（x、y、z 均为整数）是怎么求解的？
电脑死机的时候电脑在干什么？
为什么计算机刚开机就要转散热风扇？
计算机大一学生见过的最牛逼的学长或学姐可以达到什么水平？
计算复杂性理论是否具有足够的现实意义，如今有哪些比较「现实」的应用？
非高中oi选手在清华计算机系就读是什么体验？
为什么数学教材里，学生首先学习的就是算术，却不学习作为基础的集合与逻辑？
有没有哪个素数可以以多种方式写成两个正整数的平方和？
费马大定理有初等证明吗？百度文库上有的是4页有的是2页，但看着不靠铺。