2

いくつかのSO 投稿を通過した後、エラトステネスのふるいが素数を生成する最良かつ最速の方法であることがわかりました。

と という 2 つの数値の間の素数を生成したいと考えていaますb。

私の知る限り、Sieveの方法では、空間の複雑さはO(b)です。

PS: 必要なスペースを削減できるかどうかわからないので、Theta ではなく Big-O を書きました。

エラトステネスの篩で空間の複雑さを減らすことはできますか?

4

4 に答える 4

4

ここには 2 つの基本的な選択肢があります。[a..b]以下の素数で範囲をふるいにかけるsqrt(b)( Eratosthenesの「オフセット」 ふるい)、または奇数で範囲をふるいにかけます。それは正しい; 各素数の場合と同様に、各奇数の倍数を削除するだけです。範囲を 1 つのチャンクにふるいにかけるか、範囲が広すぎる場合は複数の「セグメント」に分けます (ただし、チャンクが狭すぎると効率が低下する可能性があります)。

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を追加するだけでオッズを列挙できるためです。以下のエラトステネスのふるいの「コア」素数とは異なり、sqrt(b)O (pi(sqrt(b))) = ~ 2*sqrt(b)/log(b)(ここpi()で は素数カウント関数です)。

残りの問題は、これらの「コア」素数をどのように見つけるかです。試行分割にはO(1)の追加スペースが必要になりますが、エラトステネスのふるいでそれを行う場合は、コアふるい自体を実行するために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

お気に入りの検索エンジンで「エラトステネスのセグメント化されたふるい」を検索してください。検索に行きたくない場合は、ブログに実装があります。

于 2012-09-14T20:53:15.157 に答える