4

私はかなり高速な素数ジェネレーターを実装しており、 Eratosthenes のふるいでいくつかの最適化を行って、いくつかの素晴らしい結果を得ました。特に、アルゴリズムの準備段階では、次のように 2 と 3 の倍数をすべてスキップします。

template<class Sieve, class SizeT>
void PrimeGenerator<Sieve, SizeT>::factorize()
{
    SizeT c = 2;
    m_sieve[2] = 1;
    m_sieve[3] = 1;

    for (SizeT i=5; i<m_size; i += c, c = 6 - c)
        m_sieve[i] = 1;
}

これは、エラトステネスのふるいm_sieveによるブール配列です。これは素数 2 と 3 のみを考慮した一種の Wheel 因数分解であり、パターン 2、4、2、4、.. に従って増加していると思います。

私がやりたいことは、おそらく素数 2、3、および 5 を考慮して、より大きなホイールを実装することです。

私はすでにそれに関する多くのドキュメントを読みましたが、エラトステネスのふるいを使用した実装は見当たりませんでした...サンプルコードは大いに役立ちますが、いくつかのヒントも役立ちます:)ありがとう。

4

4 に答える 4

4

さらに先に進むことができます。以下は、私が数年前に書いたいくつかの OCaml コードです。

let eratosthene borne =
  let remove_multiples a lst =
    let rec remmult multa li accu = function
        []         -> rev accu
      | head::tail ->
          if multa = head
          then remmult (a*(hd li)) (tl li)  accu      tail
          else remmult   multa        li (head::accu) tail
    in
    remmult (a * a) lst [] lst
  in
  let rec first_primes accu ll =
    let a = hd ll in 
    if a * a > borne then (rev accu) @ ll 
    else first_primes (a::accu) (remove_multiples a (tl ll))
  in
  let start_list =
(* Hard code of the differences of consecutive numbers that are prime*)
(* with 2 3 5 7 starting with 11... *) 
    let rec lrec = 2 :: 4 :: 2 :: 4 :: 6 :: 2 :: 6 :: 4 :: 2 :: 4 :: 6
      :: 6 :: 2 :: 6 :: 4 :: 2 :: 6 :: 4 :: 6 :: 8 :: 4 :: 2 :: 4 :: 2
      :: 4 :: 8 :: 6 :: 4 :: 6 :: 2 :: 4 :: 6 :: 2 :: 6 :: 6 :: 4 :: 2
      :: 4 :: 6 :: 2 :: 6 :: 4 :: 2 :: 4 :: 2 :: 10 :: 2 :: 10 :: lrec 
    and listPrime2357 a llrec accu =
      if a > borne then rev accu
      else listPrime2357 (a + (num (hd llrec))) (tl llrec) (a::accu)
    in
    listPrime2357 (num 11) lrec []
  in
  first_primes [(num 7);(num 5);(num 3);(num 2)] start_list;;

OCaml が巡回リンクリストを可能にする素晴らしいトリックに注意してください。

于 2013-07-26T23:01:33.097 に答える
3

IBM で働くオーストラリアの数学者であるポール プリチャードは、1980 年代に一連の車輪ふるいを開発しました。そのうちの 1 つについては、手動で作業した例や Scheme での実装を含めて、私のブログで説明しています。ここで議論するには大きすぎる。漸近的な複雑さはエラトステネスのふるいよりも小さくなりますが、実装の詳細により、実際には通常は遅くなることに注意してください。

于 2013-07-26T23:21:19.080 に答える
2

2*3*5 = 30
スポーク = 2,3,4,5,6,8,9,10,12,15,16,18,20,24,30
スポーク間の数: 1,7,11,13, 17,19,23,25,29 

int[] gaps = [6,4,2,4,2,4,2,4];
int[] primes = [2,3,5];
int max = 9001;
int counter, max_visited;
while(max_visited < max) {
  int jump = gaps[counter];
  counter = counter + 1 % gaps.length;
  max_visited += jump;
}

それは役に立ちますか？

または、代わりにこれが必要だった可能性があります。疑似コード:

primes = [2,3,5];
product = multiply(primes);//imaginary function that returns 30
wheel = new int[product];
foreach(prime in primes)
  for(int x = 1; x <= product/prime; x++)
    wheel[prime*x] = 1;
return wheel
于 2013-07-26T23:22:39.097 に答える
0

それのはるかに優れた最適化があります（バリアントでは O(n log log n) ではなく O(n) 操作が必要です）：https://stackoverflow.com/a/17550147/2559094、より多くのメモリが必要です（ n ではなく n + n/log n メモリ)。

引き続き最適化を行い、素数 p1、p2、...、pn を検討する場合は、0 から p1*p2*...*pn までのすべての数値を記述する必要があります (使用しない場合は lcm を使用してください)。 x != 0 (mod p1) x != 0 (mod p2) ... x != 0 (mod pn)

次に、これらの数値間のすべてのギャップを見つけ、それらのギャップの配列を作成して使用する必要があります。

于 2013-08-02T19:19:46.013 に答える