有效存储素数

Question

对于库,我需要将第一个素数存储到极限L.此集合必须具有O(1)查找时间(以检查数字是否为素数)并且必须很容易,给定数字,找到下一个素数(假设它小于L).

鉴于L是固定的,生成清单的Eratostene筛子很好.现在,我使用一个打包的布尔数组来存储列表,该列表仅包含3到L(含)之间的奇数的条目.这需要(L-2)/ 2位内存.我希望能够在不使用更多内存的情况下静态增加L.

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

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

Answer 1

您可以显式检查更多素数以删除冗余.

目前你只做了两次,通过明确检查两个可分性,然后只存储奇数数字是否为素数.

对于2和3,你会得到0到5的余数,其中只有1和5不能被2或3整除,并且可以得到素数,所以你可以得到1/3.

对于2,3和5,您可以从30个中获得8个数字,这可以很好地存储在一个字节中.

这在这里有更详细的解释.

Answer 2

打包位图和滚轮的替代方案 - 但在某些情况下同样有效 - 是存储连续素数之间的差异.如果你像往常一样省略数字2,那么所有差异都是均匀的.存储差值/ 2,您可以使用字节大小的变量获得最多2 ^ 40ish个区域(就在1999066711391之前).

2 ^ 32的素数仅需要194 MByte,而仅有赔率的打包位图需要256 MByte.迭代delta存储的素数比轮式存储快得多,轮式存储包括称为仅赔率位图的模2轮.

对于从1999066711391开始的范围,需要更大的单元尺寸或可变长度的存储.即使使用非常简单的方案,后者也可以非常高效(例如,在添加字节<255之后继续添加,如LZ4式压缩),因为间隙的频率极低于510/2.

为了效率,最好将范围划分为部分(页面)并管理它们的B树样式.

对差异进行熵编码(霍夫曼或算术编码)将永久存储要求减少到一半以下,这接近理论最优值并且比使用最佳可用封隔器压缩的列表或车轮更好.

如果数据以未压缩的方式存储,那么它仍然比二进制或文本数字的文件紧凑得多,数量级或更多.使用B树样式索引,可以根据需要简单地将部分映射到内存中,并以极快的速度迭代它们.