Leetcode204 求N以内的质数能做到空间O(1)嘛？

今天面试，遇到了一个leetcode 204， 求n以内的质数个数。我写了个空间On的，面试官让我优化空间， 我想了半天，没法优化啊， 想听听各位大佬的想法， 这个咋On的空间咋优化捏？。

分段筛法就行，每次筛O(SQRT(N))长度的就可以降到O(SQRT(N))了

Miller-Rabin prime test?

https://www.geeksforgeeks.org/primality-test-set-3-miller-rabin/

O(1)不知道 O(sqrt(n)) 还是很容易想到的吧

时间换空间呗，每一个数都筛法筛一次

ktays 发表于 2019-9-14 07:40
Miller-Rabin prime test?

https://www.geeksforgeeks.org/primality-test-set-3-miller-rabin/

这个确实满足条件，不过面试面这个似乎有点过分吧...