0

对于加载 5100 万个素数然后迭代它们的任务，最好的数据结构（在 java 中）是什么？

例如，我需要知道介于 1000000000 和同一个数减去 100000 之间的素数。

4

11 回答 11

6

对于这些数据，二分搜索不会很好，因为质数的前半部分将比它们的后半部分更接近。

您可以通过了解x 下有多少个素数来改进您的搜索。也许通过使用链接中提到的近似值来倾斜切割。

我的第一次尝试就是这个。我有两个数组。

  1. 所有素数的数组。
  2. 一个数组，它告诉我第一个数组中 1000*n 以上的第一个素数在哪里。因此，如果我想找到值为 5000 或更大的第一个素数，我会查看 secondArray[5000/1000-1]。

在对数组 1 做任何事情之前，我会在数组 2 上得到一个粗略的位置。

于 2009-07-04T02:43:51.083 回答
3

为什么要将它们存储在地图中？这样你就可以快速查找任何给定的数字是否是素数？这将是有道理的，并且可以让您快速访问。通过设置 TreeMap 的初始容量，可以减轻（但不能消除）添加它们的成本。然而，这仍然会产生树重新平衡成本。

另一种存储方式可能是简单地对它们进行排序并将它们放入一个数组中。这将为您提供具有二分搜索的 O(log n) 查找，但会使获取范围变得微不足道。您可以使用Arrays.binarySearch()。

于 2009-07-04T02:27:18.920 回答
3

由于您可以预先计算所有素数，并且（通过 Nosredna 和其他人提到的素数定理）您知道会有多少，您可以使用固定结构 (int[]) 和一次性按顺序插入成本不应该是一个问题。

二进制搜索（As Arrays.binarySearch()）会非常快，您可能不需要考虑优化。但是，您也可以使用素数定理对第 N 个素数的大致位置的预测来更快地找到范围的端点。

只是为了不同，我要指出的是，在这种规模下，您还可以将素数作为设置位存储在一个大位字段中，如果 N 是素数，则位 #N 设置为 1。结构实际上会小于int[] -- 10 亿位约为 110MiB，而 5100 万位约为 200MiB。请参阅类 BitSet。由于没有偶数索引是素数，因此您可以继承或包装 BitSet 以在传递给/从 BitSet 之前适当地为所有偶数索引和 half/double 值给出简单的答案，从而将整个字段存储在 ~55MiB 中。

测试具有这种结构的素数是 O(1)，但迭代所有设置位（素数）取决于您目标范围内素数的密度。不过，它仍然应该很快。

于 2009-07-04T04:15:37.340 回答
1

在我看来，一个简单的数组（或 ArrayList，因为它更容易使用）就可以了。添加元素是 O(1)，您可以通过对第一个素数 >= x 进行二分搜索来获得 x 和 y 之间的所有素数（参见http://java.sun.com/j2se/1.5.0/docs/ api/java/util/Collections.html#binarySearch%28java.util.List,%20T%29），然后遍历列表直到找到素数 > y。

（我意识到 cletus 打败了我，但希望额外的细节有一些用处。）

于 2009-07-04T02:30:36.930 回答
1

第 n 个素数约为p(n) ~ n ln(n)，即

p(51E6) ~ 905114146 < 2147483647 = Integer.MAX_VALUE

这意味着存储前 5100 万个素数的最有效方法是int[].

于 2009-07-04T03:30:39.227 回答
1

这完全取决于操作和使用的平衡。一个简单的排序数组最适合存储素数。

现在，如果性能确实非常重要并且内存成本微不足道，那么您可以使用索引索引来增加它。例如

int MAX_NUM_PRIMES =    ...   // the maximum number of primes to be stored
int MAX_PRIME = ....          // the largest prime to be stored
int primes[MAX_NUM_PRIMES]    // array of prime numbers, sorted
int nextPrime[MAX_PRIME]      // nextPrime[i] is the index of the next prime >= i

where nextPrime[i] is the starting point in the array primes for the first prime > i.

then, to iterate over e.g.   2000 primes from   3456, you would do

int j = nextPrime[3456]
for (i = j; i < j + 2000; i++) {
    int x = prime[i];
    ... do whatever with x ...
}
于 2009-07-04T03:42:34.930 回答
1

例如，我需要知道介于 1000000000 和同一个数减去 100000 之间的素数。

然后为您感兴趣的那些数字建立一个筛子。计算下面的所有素数是一种浪费，除非您想确切地知道有多少素数低于 999900000。

对于这种大小的数字，一个好的数据结构是位设置的。因为大约 21 个数字中有一个是素数，所以它比显式存储数字占用更少的内存，而且它对于遍历范围来说足够快。

编辑：具体来说，在我的笔记本电脑上用 Java 筛选整个范围需要一分钟多一点，筛选最后 100000 个大约需要 30 毫秒。

于 2009-07-04T06:14:18.760 回答
0

如果您想要最好的数据结构来快速找到 x 和 y 之间的素数（如您的示例中所示），您需要Binary Indexed Tree。

这里有一个很好的描述。

于 2009-07-04T05:06:40.897 回答
0

这个java小程序似乎相当快：从1到1 000 000 000 000的素数表http://www.walter-fendt.de/m14e/primes.htm（虽然没有来源，但你可以试试作者）

于 2009-07-04T06:45:16.243 回答
0

一组数字可能会很好:)

问题可能是生成数组？在这种情况下，创建一个包含数组的对象并填充它（通过生成它们或从素数列表中读取）。完成后，将其序列化到磁盘，以便程序将来可以快速读取二进制流以加载数组。

有关如何生成素数数组的变体，请参阅此问题：素数计算乐趣

于 2009-07-04T14:52:38.127 回答
0

根据您的要求，您应该使用 Eratosthenes 的分段筛。它不需要大量的内存..

找到所有素数直到 999900000. (~31,621) 的平方根，这可以很容易地存储在一个数组中。

现在，对 100000 长度的数组执行筛分过程。用这些素数。

非常有效，适用于大量数据。

于 2010-06-28T12:31:41.413 回答