冷晓晴 发表于 2025-6-1 18:38:26

筛法-OI-WIKI

筛法

OI-WIKI
该随笔由OI-WIKI而来，只不过添加了我对代码的注释和一些缺失的。方便以后查询。
埃氏筛

如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。
时间复杂度为：\(O(n \log{\log n})\)
int ehrlich(int n) {    vector visit(n + 1); // 默认所有数是质数    for (int i = 2; i
页: [1]
查看完整版本: 筛法-OI-WIKI