gpt4 book ai didi

c++ - 带轮分解的埃拉托色尼筛法

转载 作者:太空狗 更新时间:2023-10-29 20:14:06 26 4
gpt4 key购买 nike

我正在实现一个相当快的素数生成器,并且通过对 sieve of 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 是一个根据 Eratosthenes 筛法的 bool 数组。我认为这是一种仅考虑素数 2 和 3 的 Wheel 分解,按照模式 2、4、2、4、.. 递增。

我想做的是实现一个更大的轮子,也许考虑素数 2,3 和 5。

我已经阅读了很多关于它的文档,但我没有看到任何使用埃拉托色尼筛法的实现...示例代码可能会有很大帮助,但也有一些提示会很好:)谢谢。

最佳答案

你可以走得更远。这是我几年前写的一些 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++ - 带轮分解的埃拉托色尼筛法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17892313/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com