对于图书馆，我需要将第一个素数存储到限制 L。这个集合必须有 O(1) 查找时间（检查一个数字是否是素数）并且它必须很容易，给定一个数字，找到下一个素数（假设它小于 L）。
鉴于 L 是固定的，生成列表的 Eratostene 筛子就可以了。现在，我使用压缩布尔数组来存储列表，其中仅包含 3 到 L（含）之间奇数的条目。这需要 (L-2)/2 位内存。我希望能够在不使用更多内存的情况下静态增加 L。
是否存在使用较少内存且具有相似属性的数据结构？或者至少有恒定的查找时间？（然后可以枚举奇数，直到我们得到一个素数）
（我写这个的语言是Factor，但这个问题在任何具有内置或易于编程的打包位数组的语言中都是相同的）
您可以显式检查更多素数以消除冗余。
目前，您仅对两个执行此操作，即明确检查是否可被两个整除，然后仅存储奇数是否为素数。
对于 2 和 3，你得到余数 0 到 5，其中只有 1 和 5 不能被 2 或 3 整除，并且可以导致素数，所以你只剩下 1/3。
对于 2、3 和 5，您会从 30 个数字中得到 8 个数字，这很适合存储在一个字节中。
此处将对此进行更详细的说明。
打包位图和轮子的替代方案 - 但在某些情况下同样有效 - 是存储连续素数之间的差异。如果您像往常一样忽略数字 2，那么所有差异都是偶数。存储差异/2，您可以使用字节大小的变量获得多达 2^40 个区域（就在 1999066711391 之前）。
向上 2^32 的素数只需要 194 MByte，而仅赔率打包位图需要 256 MByte。迭代 delta 存储的素数比轮式存储快得多，轮式存储包括称为仅赔率位图的模 2 轮。
对于从 1999066711391 开始的范围，需要更大的单元格大小或可变长度存储。即使使用非常简单的方案，后者也可能非常有效（例如，继续添加直到添加了一个 < 255 的字节，就像在LZ4式压缩中一样），因为超过 510/2 的间隙的频率极低。
为了效率起见，最好将范围划分为部分（页面）并以 B-Tree 样式管理它们。
对差异进行熵编码（霍夫曼或算术编码）将永久存储需求减少到不到一半，这接近于理论上的最优值，并且比使用最佳可用打包器压缩的列表或轮子更好。
如果数据以未压缩的方式存储，那么它仍然比二进制或文本数字文件更紧凑，数量级或更多。有了 B-Tree 风格的索引，就很容易根据需要简单地将部分映射到内存中，并以惊人的速度迭代它们。
目前，您将 2 视为特殊情况，然后拥有一个数组，其中每个奇数都映射到数组中的一个元素（一些奇数是素数）。您可以通过将 2 和 3 视为特殊情况来改进这一点，认识到其余素数的形式为 6n+1 或 6n-1（即对于 p > 3、p mod 6 = 1 或5）。这可以进一步概括 - 参见Wikipedia。对于所有素数 p > 5，p mod 30 = 1, 7, 11, 13, 17, 19, 23 或 29。您可以继续这样做并以处理时间为代价减少所需的内存（尽管它仍然会是O(1)，只是一个较慢的 O(1))。
也许您正在寻找仅包含素数的trie数据结构。您可以使用整数数字，而不是使用字符作为索引。一个实现是Judy-Array s。
尽管如此，它们不满足您的 O(1) 要求，它们对于类似的键（就像大多数数字一样）具有极高的内存效率，并且使用 O(m) (m=key-length) 查找时非常快最大。
如果您在预先生成的树中查找素数，您可以遍历树直到找到它，或者您已经在前一个和后一个素数旁边的节点处。
某种哈希表怎么样？
您将需要一个非常好的哈希函数（类似于n mod p，其中p不是任何q最低素数的倍数 - 选择q足够高以最小化冲突次数）。
区间树怎么样？http://www.geeksforgeeks.org/interval-tree/
它可能不是 O(1)，但它真的很快。就像 O(log(p(n))) 一样，其中 p(n) 是直到数字 n 的素数数。这样，您需要的内存将仅与素数的数量成正比，从而大大降低了内存成本。
例如，假设您在 p1 找到一个素数，然后在 p2 找到下一个素数，插入区间 (p1,p2) 等等，当您搜索该范围内的任何数字时，它将返回此区间，您可以返回 p2这将是您的情况的答案。
如果您可以找出哪些是梅森或其他容易表示的素数，您可以通过使用带有适用数字标志的表示来节省一些位。
另外，如何将数字存储为与前一个数字的差异？那么大小不应该增长得那么快（但查找会很慢）。结合上述方法，您可以存储梅森素数以及与上一个梅森素数的差值。