java - 快速迭代具有 5100 万个素数的数据结构

Question

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

例如，我需要知道 1000000000 和该数字减 100000 之间的素数。

Answer 1

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

了解 how many primes there are under x 或许可以改进您的搜索。也许通过使用链接中提到的近似值来倾斜切割。

<小时/>

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

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

在对数组 1 进行任何操作之前，我会先了解数组 2 的大致位置。