减少Eratosthenes筛子的空间复杂度以产生一定范围内的素数
在经历了一些
所以帖子
，我发现
Eratosthenes的筛子
是生成质数的最好、最快的方法。
我想生成两个数字之间的质数，比方说
和
..。
AFAIK，在Sieve的方法中，空间复杂度是
O(b)
..。
PS:我写了Big-O而不是Theta，因为我不知道空间需求是否可以减少。
我们能降低空间复杂度吗？
Eratosthenes的筛子
什么？
回答 4
Stack Overflow用户
发布于 2012-09-15 04:18:56
如果您有足够的空间来存储到sqrt(b)的所有素数，那么您可以使用额外的空间O(b-a)来筛选a到b范围内的素数。
在Python中，这可能类似于：
def primesieve(ps,start,n):
"""Sieve the interval [start,start+n) for primes.
Returns a list P of length n.
P[x]==1 if the number start+x is prime.
Relies on being given a list of primes in ps from 2 up to sqrt(start+n)."""
P=[1]*n
for p in ps:
for k in range((-start)%p,n,p):
if k+start<=p: continue
P[k]=0
return P您可以通过只筛选奇数来轻松地使其占用一半的空间。
Stack Overflow用户
发布于 2012-09-19 23:20:42
这里有两个基本选择:筛选范围
由下面的素数
(
“偏移”
Eratosthenes的筛子
)，或通过
奇数
..。没错，只要去掉每个奇数的倍数，就像去掉每个素数的倍数一样。在一个块中筛选范围，如果范围太宽，则在几个“段”中筛选(但如果块太窄，效率可能会降低)。
在Haskell
可执行伪代码
-- foldl :: (r -> x -> r) -> r -> [x] -> r -- type signature of foldl
primesRange_by_Odds a b =
foldl (\ r x -> r `minus` [q x, q x+2*x .. b])
[o, o+2 .. b] -- initial value of `r`, the list
[3, 5 .. floor(sqrt(fromIntegral b))] -- values of `x`, one after another
where
o = 1 + 2*div a 2 -- odd start of the range
q x = x*x - 2*x*min 0 (div (x*x-o) (2*x)) -- 1st odd multiple of x >= x*x in range根据赔率进行筛选将会有额外的
空间
复杂性
O(1)
(在输出/范围空间的顶部
O(|b-a|)
)。
这是因为我们可以通过迭代添加
2
-与Eratosthenes筛子的“核心”素数不同，如下所示
，为此我们必须预留额外的空间
O(pi(sqrt(B)
=~
(其中
是
素数计数函数
)。
剩下的问题是我们如何找到这些“核心”质数。试验划分将需要额外的空间
O(1)
但是如果我们要用Eratosthenes的筛子来做这件事，我们需要
O(sqrt(b))
执行核心筛子本身的空间--除非我们将其作为
分段
因此具有辅助空间需求的筛子
O(sqrt(sqrt(B)
..。选择更适合您需求的方法。
Stack Overflow用户
发布于 2012-09-15 03:17:01
索伦森筛
如果空间复杂性真的是一个问题，可能值得一看。从你分享的维基百科页面上找到了参考资料。
https://stackoverflow.com/questions/12430495
复制相似问题
腾讯云开发者
