为什么埃式筛法的时间复杂度是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
相关话题
请问是质数更多还是合数更多还是一样多？如何评价姜新文老师提出的NP=P这篇文章？
如何看待全球超级计算机 TOP 500 榜单日本登顶，中国跌出前三？近年中国超算发展现状如何？
有哪些看起来很简单证明起来却很难的问题？
为什么埃式筛法的时间复杂度是O(nloglogn)？
用数据线连接手机和电脑后，可以在手机上访问电脑硬盘中的文件吗?
现在越来越多大学生转cs，那计算机专业会不会供大于求？
圆周率π的这个用正切半角表示的无穷级数展开式怎么证明?
10的100次方内的素数的中位数在什么范围内，你可以估算到多高的精度?
IOI国际金牌是什么水平，在此之上更高的水平是什么样的？
前一个讨论
为什么癌症病人眼中会产生切伦科夫光？
下一个讨论
最难的数学有多难？
相关的话题
如何看待赵盛烨这篇《云与地震的相关性研究及其实践成果综述》？级数求积：是否有一般的收敛判别法？以及实例∏[p是素数] p/(p-1) 是否收敛?
用数据线连接手机和电脑后，可以在手机上访问电脑硬盘中的文件吗?
脑机接口和成熟的基因编辑是否会改变世界?
如果世界是虚拟的，那么这个世界是“并行”的还是“并发”的?
十进制有什么优点？为什么世界各地的数学不约而同的选择了十进制？
如何从零开始准备大学生数学建模比赛？
理工科少女到底学什么在你乎才是政治正确？
如果让你重新开始学计算机，你的学习路线会是怎么选择?
王垠的《谈谈Parser》是在回应 winter 吗？
如何通俗地解释一下 TCP/UDP 协议和 HTTP、FTP、SMTP 等协议之间的区别？
对神经网络某一层做了小改进，效果却提升显著，可以发论文吗？
TensorFlow 中 padding 的 SAME 和 VALID 两种方式有何异同？
如何看待部分OIer有组织的作弊参加力扣周赛？
如何解释「线性回归」的含义？
如何看待菲尔兹和阿贝尔奖双料得主 Michael Atiyah 宣称自己证明了黎曼猜想？
是不是任意一个无理数都对应一个三角和描述？
如果比尔盖茨生在中国，仅以在微软工作期间在工程方面的贡献能评得上工程院院士吗？
数学家下围棋，水平一定会很高吧？
你相信质数会有递推表达式，或者有简单的几何形态吗？
一个数列是柯西列也是整数列，如何证明其收敛于整数?
如何实现一个简单的虚拟机？
你写代码的起手式是什么样的？
对于编程思想和能力有重大提升的书有哪些?
用计算器打 CS，实际上真的可以实现吗？
Shamir秘密共享门限方案当模数为多项式大时，为什么不安全？
生育多少个子女才能保证自己的所有染色体“几乎”都传递给下一代？
如何看待艾隆.马斯克开办的Ad Astra高中取消了传统高中的外语，音乐等课程?
如何评价深度学习之父Hinton发布的Capsule论文？
计算机专业的学生如何系统的学习前端技术？