埃拉托色尼的筛轮分解 [英] Sieve of Eratosthenes with Wheel Factorization

问题描述

我采取一个相当快的素数生成器，我得到了一些不错的结果与埃拉托色尼的筛几个优化。具体地，该算法的preliminary部分期间，我跳过的2和3的倍数的所有这样：

i'm implementing a reasonably fast prime number generator and i obtained some nice results with a few optimizations on the sieve of eratosthenes. In particular, during the preliminary part of the algorithm, i skip all multiples of 2 and 3 in this way:

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，以下递增的格局2，4，2，4，......我想这样做是为了实现一个更大的车轮，也许考虑质数2,3和5。 我已经读了很多关于它的文档，但我没有看到埃拉托色尼的筛任何实现...样品code可以有很大的帮助，但也有一些提示，将是不错的:) 谢谢你。

Here m_sieve is a boolean array according to the sieve of eratosthenes. I think this is a sort of Wheel factorization only considering primes 2 and 3, incrementing following the pattern 2, 4, 2, 4,.. What i would like to do is to implement a greater wheel, maybe considering primes 2,3 and 5. I already read a lot of documentation about it, but I didn't see any implementation with the sieve of eratosthenes... a sample code could help a lot, but also some hints would be nice :) Thanks.

推荐答案

您可以走得更远。下面是一些OCaml的code我几年前写的：

You can go even further. Here is some OCaml code I wrote a few years ago:

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的允许循环链表。

Note the nice trick that OCaml allows for cyclic linked list.

这篇关于埃拉托色尼的筛轮分解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！