c – 具有车轮分解的Eratosthenes筛

发布时间：2020-12-16 09:46:34 所属栏目：百科来源：网络整理

导读：我正在实现一个相当快速的素数发生器,我通过对eratosthenes筛子的一些优化获得了一些不错的结果.特别是,在算法的初步部分,我以这种方式跳过所有2和3的倍数： templateclass Sieve,class SizeTvoid PrimeGeneratorSieve,SizeT::factorize(){ SizeT c = 2; m_s

我正在实现一个相当快速的素数发生器,我通过对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;
}

根据eratosthenes的筛子,m_sieve是一个布尔数组.
我认为这是一种只考虑素数2和3的车轮分解,按照模式2,4,2,4进行递增.我想要做的是实现更大的轮子,可能考虑质数2,3和5.
我已经阅读了很多关于它的文档,但是我没有看到任何关于eratosthenes筛选的实现…示例代码可以帮助很多,但也有一些提示会很好:)
谢谢.

解决方法

你可以走得更远.这是几年前我写的一些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允许循环链表的好技巧.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!