素数的有效存储 [英] 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)

（我写的这个语言是因子，但这个问题在任何内置或易于编程的打包位阵列的语言中都是一样的）

(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.

目前只做两件事，通过检查可分割性两个明确地然后只存储奇数，不管它们是否是素数。

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，你可以得到8个数字，这是很好的存储在一个字节。

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

这更详细地解释了 here 。

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