如果我没看错的话，这个代码复杂度是 $\mathcal O(n \log n \log \log n)$，$n = 10^8$ 显然过不了。
by _sunkuangzheng_ @ 2024-01-01 22:31:22
@[_sunkuangzheng_](/user/923947) 啊？渐进时间复杂度应该是O(n)吧，每个数的map都只被置位了最多一次，判断次数也是一次
您是不是把我的map变量看成了std::map了，我寻思时间复杂度怎么算也算不出lg啊
by yiming564 @ 2024-01-01 22:44:17
@[yiming564](/user/554746) 抱歉我确实看成 std::map 了，还好奇为什么跑这么快（）
去掉那个的话这是埃氏筛的复杂度，是 $\mathcal O(n \log \log n)$ 捏。
by _sunkuangzheng_ @ 2024-01-01 22:51:35
@[_sunkuangzheng_](/user/923947) （眼前一黑
感谢指出错误orz
by yiming564 @ 2024-01-01 22:57:29
@[yiming564](/user/554746) 建议学 $O(n)$ 线性筛
by heyx0201 @ 2024-01-02 01:44:39
题解区有优化的
by Sqj147 @ 2024-02-02 22:49:39