math - 有效存储质数

Question

对于图书馆，我需要存储第一个质数，直到上限L。该集合必须具有O(1)查找时间(以检查数字是否为质数)，并且给定一个数字必须很容易，查找下一个质数(假设它小于L)。

假设L是固定的，则可以用Eratostene筛子生成列表。现在，我使用一个压缩的 bool(boolean) 数组来存储列表，该列表仅包含3到L(含)之间的奇数的条目。这需要(L-2)/ 2位内存。我希望能够在不使用更多内存的情况下静态地增加L。

是否存在使用较少内存且具有类似属性的数据结构？还是至少具有恒定的查找时间？ (然后可以枚举奇数，直到我们得到素数)

(我写的语言是Factor，但是这个问题在具有内置或易于编程的打包位数组的任何语言中都是相同的)

Answer 1

您可以显式检查更多质数以消除冗余。

目前，您只需要对两个对象执行此操作，方法是显式检查两个对象的除数，然后仅存储奇数是否为质数。

对于2和3，您会得到0到5的余数，其中只有1和5不能被2或3整除，并且可以导致质数，因此您降低到1/3。

对于2、3和5，您会从30个数字中得到8个数字，可以将其存储在一个字节中。

here对此进行了更详细的说明。