关于线性筛的空间复杂度

学术版

ningago @ 2022-07-01 13:11:22

RT.

有没有不依赖bool vis[10^8]的低空间复杂度做法？

by fjy666 @ 2022-07-01 13:11:57

bitset

by fjy666 @ 2022-07-01 13:12:36

比 O(n/w) 还低我就不会了

by NikaidouHiro @ 2022-07-01 13:13:48

@ningago 只有bitset O(\dfrac nw)

by __stick @ 2022-07-01 13:24:10

不是有个空间限制 1 MB 的线性筛题目吗

by 蒟蒻君HJT @ 2022-07-01 13:43:35

oiwiki useless

by houzhiyuan @ 2022-07-01 13:58:23

可以再特判 2,3 等小质数，空间复杂度比 O(\frac{n}{w}) 更小，如果只判这两个是除以 3。

by uibn @ 2022-07-01 14:42:19

原来用bitset会变慢？！难怪我线性筛一直跑的很慢？

|