为什么埃式筛法的时间复杂度是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
相关话题
有没有比图灵机能力更强的计算模型？在苏联时期苏联人用什么计算机？
什么才算是真正的编程能力？
做一个不同编程语言之间的converter有没有意义？
机械类的优秀答主为什么那么少？
明年毕业，导师想给我15k工资让我留本校读博，我要怎么选择？
如何证明对于任意的正整数n，若p整除n^2+n+1，则p模3一定不余2？
如果打算证明黎曼猜想，请问从大一开始应该做什么数学基础准备？
不会计算机的废物大学生有活着的必要吗？
那些曾经大名鼎鼎的黑客，现在怎么样了？
前一个讨论
为什么癌症病人眼中会产生切伦科夫光？
下一个讨论
最难的数学有多难？
相关的话题
计算机领域有哪些经典的典故或笑话？算法竞赛如何训练数论这一块？
为什么埃式筛法的时间复杂度是O(nloglogn)？
编程入门门槛真的很低吗？
C/Ｃ++ 标准库为什么不支持直接删除一个文件中的部分内容？
为什么大家都说程序员需要好键盘？
如何看待菲尔兹和阿贝尔奖双料得主 Michael Atiyah 宣称自己证明了黎曼猜想？
自然数 n 的因数个数的数量级估计？
摩尔定律是正确的么？
电子（EE）专业犹豫要不要研究生转计算机专业（CS）？
两相邻素数的最大间距能够多大？
想裸写编译器，除了编译原理外还有那些资料可以参考？应该从什么开始写起？（用c/c++）？
是否存在一个复解析函数f(z)，使得对于正整数n，f(n)就是第n个质数？
为什么CPU主频一般都比FPGA快，但是却说FPGA可以帮助CPU加速？
如何评价中科大潘建伟团队在「祖冲之号」量子计算原型机上展示的量子计算优越性？这是怎样实现的？
虚拟地址、线性地址、物理地址之间是如何转换的？
如果计算机没有浮点运算能力，系统能正常启动吗？
编程语言发展史上有哪些趣事？
为什么计算机刚开机就要转散热风扇？
2022 年最适合写业务代码的编程语言是哪个？
如何看待清华大学 2018 年转系申请结果？
为什么很多计算机系的学生一点不会电脑的基本操作？
如果比尔盖茨生在中国，仅以在微软工作期间在工程方面的贡献能评得上工程院院士吗？
你写过的自己觉着最牛的黑程序是什么？
如何评价王垠《计算机科学入门班报名》收费12000？
如何让自己的英文学术写作能力接近英语母语者的水平？
为什么现在有这么多人工智能无用论？
为什么大多数程序主函数成功时都return 0; 不return 1; ？
可以用ACM/ICPC竞赛成绩来判定一个高校的计算机专业水准吗?
为什么在项目中要尽量避免使用浮点数，不使用浮点数，那该如何计算浮点数？