c – 具有车轮分解的Eratosthenes筛

概述我正在实现一个相当快速的素数发生器,我通过对eratosthenes筛子的一些优化获得了一些不错的结果.特别是,在算法的初步部分,我以这种方式跳过所有2和3的倍数： template<class Sieve, class SizeT>void PrimeGenerator<Sieve, SizeT>::factorize(){ SizeT c = 2; m_sieve[2] = 我正在实现一个相当快速的素数发生器,我通过对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允许循环链表的好技巧.

总结

以上是内存溢出为你收集整理的c – 具有车轮分解的Eratosthenes筛全部内容，希望文章能够帮你解决c – 具有车轮分解的Eratosthenes筛所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。