2

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

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

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

PS：我写的是Big-O而不是Theta，因为不知道能不能减少空间需求。

我们可以降低埃拉托色尼筛中的空间复杂度吗？

4

4 回答 4

4

这里有两个基本选择：[a..b]通过以下素数筛选范围sqrt(b)（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(|ba|)的输出/范围空间之上）。

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

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

于 2012-09-19T15:20:42.173 回答
2

如果空间复杂度真的是一个问题， Sorenson Sieve可能值得一看。从您共享的维基百科页面获得参考。

于 2012-09-14T19:17:00.937 回答
1

如果您有足够的空间来存储直到 sqrt(b) 的所有素数，那么您可以使用额外的空间 O(ba) 筛选 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

你可以很容易地通过只筛选奇数来减少一半的空间。

于 2012-09-14T20:18:56.083 回答
1

在您最喜欢的搜索引擎中搜索“Eratosthenes 分段筛”。如果你不想去搜索，我在我的博客上有一个实现。

于 2012-09-14T20:53:15.157 回答