降低埃拉托斯特尼筛法的空间复杂度以生成一定范围内的素数

Question

在浏览了一些SO 帖子后，我发现埃拉托色尼筛法是生成素数的最佳且最快的方法。

我想生成两个数字之间的素数，例如a和b。

AFAIK，在 Sieve 方法中，空间复杂度为O(b)。

PS：我写的是Big-O而不是Theta，因为我不知道空间要求是否可以减少。

我们可以降低埃拉托斯特尼筛法的空间复杂度吗？

Answer 1

[a..b]这里有两个基本选择：通过下面的素数sqrt(b)（埃拉托斯特尼的“偏移” 筛）或奇数来筛选范围。这是正确的; 就像消除每个质数一样消除每个奇数的倍数。如果范围太宽，则将范围筛选为一个块或多个“段”（但如果块太窄，效率可能会下降）。

\n

在 Haskell可执行伪代码中，

\n

-- foldl :: (r -> x -> r) -> r -> [x] -> r     -- type signature of foldl\n\nprimesRange_by_Odds a b = \n  foldl (\\ r x -> r `minus` [q x, q x+2*x .. b])\n        [o, o+2 .. b]                          -- initial value of `r`, the list\n        [3, 5 .. floor(sqrt(fromIntegral b))]  -- values of `x`, one after another\n  where\n    o   = 1 + 2*div a 2                        -- odd start of the range\n    q x = x*x - 2*x*min 0 (div (x*x-o) (2*x))  -- 1st odd multiple of x >= x*x in range\n

\n

按赔率筛选将具有O(1)的额外空间复杂度（在O(|ba|)的输出/范围空间之上）。

\n

这是因为我们可以通过迭代添加2 \xe2\x80\x93来枚举几率，这与下面的埃拉托斯特尼筛的“核心”素数不同sqrt(b)，我们必须为此保留O(pi(sqrt(b))的额外空间)) = ~ 2*sqrt(b)/log(b)（其中pi()是素数计数函数）。

\n

剩下的问题是我们如何找到那些“核心”素数。试除法将需要O(1)的额外空间，但如果我们要通过埃拉托斯特尼筛法来进行，我们需要 O (sqrt(b))空间来执行核心筛法本身 - 除非我们执行它作为分段筛，因此辅助空间要求为O(sqrt(sqrt(b)))。选择更适合您需求的方法。

\n