![]() |
1
5
这个似乎工作得很好。用(1000000号筛子)对其进行了测试,并在几秒钟内返回,无需吹气。 |
![]() |
2
2
哦,在看到这个问题之前,我已经对你的另一个问题发表了评论…无论如何,埃拉托斯滕的筛子不进行余数/模计算,只进行加法(以递增的方式在列表中移动
现在,一个严格忠实的SOE需要是“有限的”,因为它只能在一个固定长度的数字数组上操作;但是,如果保留了一个额外的数据结构来记录到达的数字的信息,那么基本的算法可以修改为支持“增量”筛选(使用任意数量的素数的延迟生成)Ed到目前为止发现的每一个素数的“划掉”通行证。对于这样的数据结构,最佳选择是优先级队列,但是映射也是非常有用的。 有关基于此思想的函数语言增量筛选的扩展讨论(包括对所有涉及算法的复杂性的仔细分析),请参阅Melissa E.O'Neill的文章 The Genuine Sieve of Eratosthenes . 它使用haskell,但这不应该是一个问题(没有使用深奥的特性,haskell代码特别清晰,所以它读起来很像常规的数学符号)。 例如,在Clojure中的实现,请参见Christophe Grand的 Everybody loves the Sieve of Eratosthenes 博客条目——强烈推荐,最终版本绝对漂亮,速度也非常快——如果我可以随意在这里插入它们,也许还有几个要点: the first one , the second one . (请注意,它们一点也不漂亮,但它们对我来说是一个有用的实验……第二个队列使用优先级队列,而其他队列则基于地图,因此希望它现在可以作为一个粗略的示例使用。) 我想我并没有回答你的主要clojure实施问题,但我认为Michiel的答案和你另一个问题的主要答案之间,那个问题已经解决了。 |
![]() |
danial · 如何在多个字符串的每个位置找到最频繁的字符 2 年前 |
![]() |
Manny · 如何比较Perl中的字符串? 2 年前 |
![]() |
Diret · 获取范围内每个数字的子倍数的算法 2 年前 |
![]() |
Saif · 排序时python如何决定何时调用比较器? 2 年前 |