【水】素数筛法时间复杂度一个小疑问
  • 板块灌水区
  • 楼主fast_photon猫娘希儿
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/7/15 22:13
  • 上次更新2023/10/27 20:07:25
查看原帖
【水】素数筛法时间复杂度一个小疑问
302805
fast_photon猫娘希儿楼主2022/7/15 22:13

杜教筛的复杂度是 O(n23)O(n^{\frac{2}{3}})
但是 limninfn/ln(n)n23\lim\limits_{n\to\inf}\frac{n/\ln(n)}{n^{\frac{2}{3}}} 好像是无穷大?这说明杜教筛速度比直接遍历 nn 以内所有素数都要快?
还是同学用微积分证明的 limninf\lim\limits_{n\to\inf} 时素数个数结论错了

2022/7/15 22:13
加载中...