素数的高效存储 [英] Efficient storage of prime numbers

问题描述

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

For a library, I need to store the first primes numbers up to a limit L. This collection must have a O(1) lookup time (to check whether a number is prime or not) and it must be easy, given a number, to find the next prime number (assuming it is smaller than L).

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

Given that L is fixed, an Eratostene sieve to generate the list is fine. Right now, I use a packed boolean array to store the list, which contains only entries for odd numbers between 3 and L (inclusive). This takes (L-2)/2 bits of memory. I would like to be able to statically increase L without using more memory.

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

Is there a data structure using less memory with similar properties? Or with at least the constant lookup time? (odd numbers can then be enumerated until we get a prime)

(我写这个的语言是 Factor 但是这个问题在任何语言中都是一样的内置或易于编程的压缩位数组)

(the language I wrote this in is Factor but this question would be the same in any language which has built-in or easily programmable packed bit arrays)

推荐答案

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

You can explicitly check more prime numbers to remove redundancy.

目前，您只针对两个执行此操作，方法是明确检查是否可被 2 整除，然后仅存储奇数是否为质数.

At the moment you do this only for two, by checking for divisibility by two explicitly and then storing only for odd numbers whether they are prime.

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

For 2 and 3 you get remainders 0 to 5, of which only 1 and 5 are not divisible by two or three and can lead to a prime number, so you are down to 1/3.

对于 2、3 和 5，您可以得到 30 个数字中的 8 个，这很适合存储在一个字节中.

For 2, 3, and 5 you get 8 numbers out of 30, which is nice to store in a byte.

在此处有更详细的解释.

这篇关于素数的高效存储的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！