减少Eratosthenes筛子的空间复杂度以产生一定范围内的素数
减少Eratosthenes筛子的空间复杂度以产生一定范围内的素数
提问于 2012-09-15 03:03:56
在经历了一些
所以帖子
，我发现
Eratosthenes的筛子
是生成质数的最好、最快的方法。
我想生成两个数字之间的质数，比方说
和
..。
AFAIK，在Sieve的方法中，空间复杂度是
O(b)
..。
PS:我写了Big-O而不是Theta，因为我不知道空间需求是否可以减少。
我们能降低空间复杂度吗？
Eratosthenes的筛子
什么？
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提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12430495
复制相关文章
相似问题
腾讯云开发者
