问题标签 [sieve]

我写了以下筛子：

但我不明白为什么它在第一个值之后会卡住。运行take 10 sieve结果[2,并没有任何反应。它可能与无限递归有关。问题可能在于它sieve正在增长并且同时在内部使用isPrime？出于这个原因，我也尝试修改isPrime如下，但没有成功：

编辑：令人惊讶的是，@Jubobs 的修改有效：

我不明白为什么这个版本的takeWhile作品，而另一个没有。我看到在我以前的版本中，我测试了许多不必要的除数，但它们的数量仍然有限。

该代码应该基本上等同于以下 Python 代码：

我们知道所有大于 3 的素数都可以使用以下方法生成：

但是，我们从上述公式生成的所有数字都不是素数。

为了消除这种情况，我使用了筛法并删除了作为从上述公式生成的数字的因素的数字。

使用事实：

如果一个数没有素因数，则称它为素数。

1. 因为我们可以使用上述公式生成所有素数。
2. 如果我们可以删除上述数字的所有倍数，我们就只剩下素数了。

生成低于 1000 的素数。

但是，此方法确实可以正确生成素数。这以更快的方式运行，因为我们不需要检查我们在筛子中检查的所有数字。

我的问题是我错过了任何边缘情况吗？这会好很多，但我从未见过有人使用它。难道我做错了什么？

这种方法可以更优化吗？

用 aboolean[]代替 anArrayList会快得多。

我已经实施了阿特金筛法，它在质数接近 100,000,000 左右时效果很好。除此之外，它会因为内存问题而崩溃。

在算法中，我想用基于硬盘的阵列替换基于内存的阵列。Python 的“wb”文件函数和 Seek 函数可以解决问题。在我开始发明新轮子之前，有人可以提供建议吗？一开始就出现了两个问题：

1. 有没有办法“分块”阿特金的筛子来处理内存中的片段，以及
2. 有没有办法暂停活动并稍后再回来 - 建议我可以序列化内存变量并恢复它们。

我为什么要这样做？一个寻找娱乐和保持面条工作的老家伙。

[Python 3.4] 下面的程序是一个简单的 Eratosthenes 筛子：

它产生 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]。好的。取消注释内联 excl() 的行并注释调用，给出 [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]。为什么？

它是否与在循环中修改序列时预期的麻烦有关？

谢谢你的任何提示。

设置打印出所有错误值，这些错误值是素数，但打印出 25 个。3, 5, 7, 8, 9, 11, 13, 14, 15, 17, 19, 20, 21, 23, 24，不知道为什么其中一些会溜走。对此事的任何见解都会很好。

或者只是将我指向写入方向。为什么要打印 8 等非质数？

问题：查找

n的范围：1<= n <=

主要挑战是处理可能很大的查询（Q）。1 <= Q <=

到目前为止我使用的方法：

蛮力

复杂性：

预处理和处理查询

首先，我建立一个表，其中包含每个 N 的欧拉函数值。这可以在 O(N) 中完成。

对于每个查询，分解 N 并添加d*phi[d]到结果中。

这需要 O(sqrt(N)) 。

复杂度：O(Q*sqrt(N))

在 O(1) 中处理查询

在我上面描述的筛法中，我添加了一个计算我们在 O(NLogN) 中需要的答案的部分

不幸的是，对于给定的约束和时间限制（1 秒），这会超时。

我认为这涉及到关于 N 的素数分解的一些聪明的想法。我可以使用上面构建的 lp(lowest prime) 表对 O(LogN) 中的一个数字进行素数因式分解，但我无法弄清楚如何使用因式分解得出答案。

在以下初筛中：

是什么x | x <- xs意思x `mod` p > 0？

我正在研究一种在 Java 中创建布尔数组isPrime的方法：

其中素数标记为“真”，其余标记为“假”。
虽然我在这里，但我还想计算找到的素数：

基本思想是使用埃拉托色尼筛。到目前为止，我的方法如下所示：

所以我的问题是

不起作用，因为筛子不止一次将一些非素数的值设置为“假” （例如 45 bcs 3*15 = 45 和 9*5 = 45）。
那么有没有人知道我如何重写这个程序，以便它只将所有非质数设置为“假”一次？

或者一般来说，任何人都可以提出使该方法更快的方法吗？

这是我的素数查找算法——它工作得很好（而且非常快），直到限制设置在 173 以上，然后它开始抛出

我不明白为什么在限制为 174 或更高之前它工作得非常好——这是我的代码。

我已经为 totients 列表编写了一个基于筛子的生成器，并且希望总和达到 1000000。

当计算totientSum n超过n40000 时，ghci 需要很长时间来评估并开始消耗大量内存。编译成可执行文件没有帮助。我认为这与 Haskell 处理惰性求值的方式有关。

我想知道是否可以有选择地应用严格性来改善上述函数的内存消耗，以便我可以计算到 1000000 的总和。我还想知道是否有更好的方法来使用列表，或者如果我应该使用随机访问数据结构。如果您知道计算总和的更快算法，请分享参考。

我认为 的定义applyEvery可能会有所不同，所以我尝试了以下其他实现，但它们似乎都比上面使用的定义消耗更多的内存。