降低Eratosthenes筛的空间复杂度生成区间素数

Question

在阅读了一些SO帖子后，我发现埃拉托色尼筛是生成质数的最好和最快的方法。

我想生成两个数之间的素数，比如A和B。

我们能降低《埃拉托色尼筛》中的空间复杂性吗？

Answer 1

这里有两种基本选择：根据SQRT(b)下面的素数（埃拉托色尼的“偏移量”筛选）筛选范围[a.b]或奇数。没错；只要消除每个奇数的倍数，就像消除每个素数一样。在一个块中筛选范围，如果范围太宽，则在几个“段”中筛选（但如果块太窄，效率可能会下降）。

在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）之上）。

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