问题标签 [sieve-of-eratosthenes]

我正在尝试在 Scala中实现Eratosthenes 筛。

我首先初始化所有奇数加 2 的序列：

现在nums包含 Seq( 2,3,5,7,9,11,13,15,...,(largestPrime) )。然后，通过筛子，我想遍历每个元素，并从 Seq 中过滤该元素的所有倍数。它看起来像这样，除了这只是迭代每个奇数：

所以相反，我想使用这样的东西：

但是，当然，这只是将序列复制到一个迭代器中，然后像 for 循环开始时那样迭代每个值nums（因此在这种情况下，它与前面的示例完全相同）。我希望它每次迭代都能从nums.

实现这一点的最佳方法是什么？我应该使用索引变量和while循环吗？我不确定如何从序列中获取元素（即如何获取序列的元素 x，其中 x 是索引）。或者有没有更实用的方法来做到这一点？

编辑：我刚刚找到了这个scanLeft功能，我正在尝试掌握如何使用它，因为我怀疑它可能在这种情况下有用......

我只是在尝试（对我来说）一种新的编程语言：clojure。我写了一个非常幼稚的“筛子”实现，然后我尝试对其进行优化。

奇怪的是（至少对我来说），新的实现并不快，而是慢得多......

任何人都可以提供一些关于为什么这慢得多的见解吗？

我还对如何改进此算法的其他技巧感兴趣...

最好的祝福，

阿诺·古德

现在，我正在尝试学习 Scala 。我从小处着手，编写一些简单的算法。当我想通过查找所有低于某个阈值的素数来实现 Sieve 算法时，我遇到了一些问题。

我的实现是：

不幸的是，当我想计算所有小于 1000000 (100 万) 的素数时，它失败了。我收到 OutOfMemory 。

您对如何优化代码有任何想法，或者我如何以更优雅的方式实现此算法。

PS：我在 Haskell 中做过非常相似的事情，我没有遇到任何问题。

我对在纯功能 F# 中实现埃拉托色尼筛感兴趣。我对实际筛子的实现感兴趣，而不是不是真正筛子的天真的功能实现，所以不是这样的：

上面的第二个链接简要描述了一种需要使用多重映射的算法，据我所知，该算法在 F# 中不可用。给出的 Haskell 实现使用了一个支持方法的映射，我在F# 功能映射insertWith中没有看到该方法。

有谁知道将给定的 Haskell 映射代码转换为 F# 的方法，或者可能知道替代实现方法或筛选算法同样有效且更适合功能实现或 F#？

谁能告诉我如何在 C 中实现埃拉托色尼筛算法？我需要生成素数，但我的算法很慢。

我的代码：

t是测试用例的数量 m 和 n 是要打印素数的范围。

我是这个论坛的新手，不太了解这个论坛的协议，所以请原谅我的无知。我的问题与 spoj 问题https://www.spoj.pl/problems/KPRIMES2/有关。我正在为这个问题获得 TIME LIMIT EXCEED。我认为这个程序的瓶颈是生成 10^9。有人可以建议如何改进这个筛子，更快地生成素数或如何解决这个问题。这是我的算法的草图

该程序生成所有形式为 2k+1 的素数，并将这些素数编码为数组 a[i] 的 32 位整数，其中未设置的位表示素数。a[0] 编码 3,5,7.......65 .a[1] 从 67 开始编码，依此类推。我采用了一个辅助数组 bitcnt[]，其中 bitcnt[i] 存储了 a[0]、a[1]、.........a[i] 的未设置位的总和。我使用bitcnt进行二进制搜索并找到第k个数字的位置。这里是函数的位解释。prime() 函数生成素数，我将素数编码为数字 [32 位无符号整数] 的位。bitcnt 数组存储数组 a 的未设置位的总和，用于二进制搜索。bsearchupper(int m) 返回 m 所在的 bitcnt 的索引。最后在主函数中，我存储了多少素数达到 m 的上限并开始减小值直到我得到 K。谢谢。

编辑：来自 SPOJ 的问题陈述

输入

一个整数，表示查询的数量 Q（等于 100000），接下来是 Q 行，每行包含一个介于 1 和 50000000 之间的整数 K。

输出

Q 行与每个查询的答案：第 K 个素数。

例子

输入：8 1 10 100 1000 10000 100000 1000000 10000000

输出：2 29 541 7919 104729 1299709 15485863 179424673

这是我在 sphere online Judge 上提交的用于生成素数的代码，但我遇到了分段错误。目标是生成给定范围 m 到 n 之间的素数（n > m）。这是使用埃拉托色尼筛算法实现的。请告诉我我哪里出错了。谢谢 ：）

这是我的埃拉托色尼筛法，用于查找最大为 n 的素数。我觉得它应该可以工作，但我得到一个错误，我真的不明白为什么：

为什么会提到 x？

这是代码：

前段时间我在 python 中使用了（极快的）primesieve，我在这里找到了：Fastest way to list all primes below N

准确地说，这个实现：

现在我可以通过自动跳过 2、3 等的倍数来稍微掌握优化的想法，但是在将此算法移植到 C++ 时我卡住了（我对 python 有很好的理解，对C++，但对于摇滚乐来说已经足够了）。

我目前自己滚动的是这个（isqrt()只是一个简单的整数平方根函数）：

这个实现很不错并且会自动跳过 2 的倍数，但是如果我可以移植 Python 实现，我认为它会更快（50%-30% 左右）。

为了比较结果（希望能成功回答这个问题），在 Q6600 Ubuntu 10.10 上的当前执行时间N=100000000为g++ -O31230 毫秒。

现在，我希望能在理解上述 Python 实现的作用或为我移植它方面获得一些帮助（虽然没有那么有用）。

编辑

关于我觉得困难的一些额外信息。

我对校正变量等使用的技术以及它如何组合在一起遇到了麻烦。一个解释不同 Eratosthenes 优化的网站的链接（除了简单的网站说“你只需跳过 2、3 和 5 的倍数”然后用 1000 行 C 文件猛烈抨击你）会很棒。

我不认为我会遇到 100% 直接和文字端口的问题，但毕竟这是为了学习，这完全没用。

编辑

在查看原始 numpy 版本中的代码后，它实际上很容易实现，并且有些想法并不难理解。这是我想出的 C++ 版本。我在这里发布完整版，以帮助更多的读者，以防他们需要一个非常有效的素筛，而不是两百万行代码。这个素数筛在与上述相同的机器上在大约 415 毫秒内完成所有低于 100000000 的素数。这是 3 倍的加速，比我预期的要好！

我在一次采访中被问到这个问题。我使用埃拉托色尼筛概念和数组实现了一个算法。

有没有更好的方法来解决这个问题对于那些不知道筛子的人，这里是链接：

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

编辑：就时间和空间复杂性而言最好。我刚刚告诉他们 SoE 的缺陷是空间复杂性。所以他们问我能不能做点什么。以下是采访的进行方式： 1) 实现一个算法，打印从 1 到 n 的素数 Ans: 我使用 SoE 实现 2) 这是最好的方法吗 Ans: ???