问题标签 [sieve-of-atkin]

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

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

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

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

我在 spoj.com 上遇到了这个问题

http://www.spoj.com/problems/PRIME1/

在阅读了一些关于素数生成算法的信息后，我发现“阿特金斯筛子”是最快的素数生成算法。在本教程http://www.geeksforgeeks.org/sieve-of-atkin/的帮助下，我已经部分实现了算法

当我运行代码时，它给了我分段错误。调试后我才知道这段代码不是最优的，它使用了更多的内存和存储空间。有人可以告诉我如何优化程序。这是我的代码片段。是的，它是不完整的。

我在 C++ 中实现了 Atkin 的 Sieve 以返回 bool 类型的向量，但它没有标记某些素数。

这是给定代码的输出。2、3、11、17、19、23、29、31、41、43、47、53、59、67、71、72、79、83、89、

我究竟做错了什么 ？

我目前正在尝试在 Haskell 中实施 Atkin 筛

在关于阿特金筛子的维基百科文章的第3 步中，我需要找到多个方程的整数解的数量。

然而，我对这些方程中的第一个方程的解（4x² + y² = n, x > 0, y > 0 其中 n 是正整数列表中的一个条目）在使用任何 n 进行查询时会产生无限循环。

到目前为止，这是我解决这部分问题的代码：

它被 WinGHCi 加载得很好，但是当我查询时，eq1 0它只是停留在一个无限循环中，并且在产生答案之前必须被中断。我怀疑它在 和 的两个分配之间x循环y。

我怎样才能防止这种情况？这甚至可能吗？

编辑：意识到无限循环必须在哪里。

我正在做一个关于阿特金斯筛子的项目，我正在探索为什么要创建这个算法。据我了解，这是一种寻找素数的方法，它比埃拉托色尼筛法运行得更快。但从我所读到的，阿特金斯筛法只是理论上运行得更快，而这在实践中从未发生过。我使用 GeeksForGeeks 的这两个实现对其进行了测试，而 Eratosthenes 总是运行得更快。但我也读过像这个 wiki 页面这样的相互矛盾的观点，它说 Atkins 运行得更快，并且可以优化为理论上运行得更快。

这是维基（它在复杂性部分讨论了这个）：https ://en.wikipedia.org/wiki/Generation_of_primes

阿特金斯筛实施：https ://www.geeksforgeeks.org/sieve-of-atkin/ Eratosthenes 筛实施：https ://www.geeksforgeeks.org/sieve-of-eratosthenes/

有人可以解释哪个应该跑得更快吗？以及为什么永远无法达到阿特金斯筛的理论时间复杂度。