我试图在 600851475143 之前得到所有素数。我为此使用了埃拉托色尼筛。这需要我创建一个如此巨大的布尔数组。坏主意，你可能会耗尽内存。任何其他方式。我尝试使用字符串，使用值为 0 和 1 的每个索引来表示真或假。但 indexOf 方法也返回 int。
接下来我使用二维数组来解决我的问题。还有其他更好的方法来存储如此庞大的数组吗？
问问题
9959 次
5 回答
7
600851475143 布尔值的内存要求最多为 70Gb。这是不可行的。您需要按照 Stephan 的建议使用压缩，或者找到不同的算法来计算素数。
于 2013-04-15T12:17:44.247 回答
6
我有一个类似的问题，我使用了一个位集（基本上按顺序将 1 或 0 设置为所需的偏移量），我建议使用EWAHCompressedBitmap它也会压缩你的位集
编辑
正如 Alan 所说，BitSet 将占用 70GB 内存，但您可以做另一件事：拥有多个 BitSet（连续的 BitSet，以便您可以计算绝对位置）并将您当时需要的 BitSet 加载到内存中，就像一个懒惰的人一样加载，在这种情况下，您将控制所使用的内存。
于 2013-04-15T12:15:56.887 回答
2
您可以使用 HotSpot 的内部 sun.misc.Unsafe API 来分配更大的数组。我写了一篇博客文章如何用它模拟一个数组但是，它不是一个官方的 Java API，所以它有资格作为一个 hack。
于 2013-09-26T22:04:56.163 回答
2
记住每个数字是否是素数并不实际（对于大数来说，筛子通常是一种非常慢的方法）。
从这个链接中，您可以了解预计有多少个质数小于 X。对于您的 6000 亿范围，您可以预计在该范围内存在大约 200 亿个质数。将它们存储为 long[] 将需要大约 160GB 的内存......这比建议的 70GB 存储每个数字的单个位要多，如果排除偶数（2 是唯一的偶数），则为一半。
对于台式计算机来说，35GB 的内存可能有点多，但一个好的工作站可以有这么多的 RAM。我会尝试使用位移/屏蔽的二维数组。
我仍然希望您的筛选代码运行相当长的时间（从几天到几年）。我建议您研究比筛子更先进的素数检测方法。
于 2013-04-15T14:09:38.657 回答
0
使用BitSet。然后您可以设置位任何索引元素。因此， 600851475143 在2^39内部仅占用 39 位（实际上，它使用 long 将占用 64 位）。
您实际上可以移动到2^63对于大多数用途来说都是巨大的
于 2013-04-15T12:15:10.000 回答