高效存储质数列表

Question

这篇文章的说法如下：

每个质数都可以表示为 30k±1, 30k±7, 30k±11, 或 30k±13的形式，其中k是某个整数。 这意味着我们可以用每30个数字8位来存储所有的质数; 一百万个质数可以压缩到33,334字节。

---

"这意味着我们可以用每30个数字8位来存储所有的质数"

这里的“八位每三十个数字”是针对k的，对吗？但每个k值不一定只占用一个位。难道不应该是八个k值才对吗？

---

"一百万个质数可以压缩到33,334字节"

我不确定这是怎么实现的。

我们需要指出两件事情：

• k的值（可以是任意大的数）

• 状态，有八种形式(-13,-11,-7,-1,1,7,11,13)

我不明白“33,334字节”是怎么计算出来的，但我可以说一件事：随着质数的值越来越大，我们需要更多的空间来存储k的值。

那么，我们如何把它固定在“33,334字节”？

- Lazer

---

应该翻译为：“除了2、3和5以外的每个质数都可以表示为…” - Tyler

@MatrixFrog：当然可以，但是你的“解压程序”在处理压缩数据之前只会输出这3个。 - Steve Jessop

最紧凑的表示是英语短语“前一百万个质数”。它包含了所有需要解压缩的信息。 - Mark Adler

Answer 1

这篇文章有点误导性：我们不能存储1百万个质数，但可以存储所有小于1百万的质数。

k的值来自其在列表中的位置。对于那8个排列(-13,-11..,11,13)，我们只需要1位。

换句话说，对于k=0，我们将使用8位进行存储，对于k=1，我们将使用8位进行存储，对于k=2，我们也是使用8位进行存储，以此类推。通过让它们按顺序跟随，我们不需要为每8位指定k的值-它只是前8位的值+1。

由于1,000,000 / 30 = 33,333 1/3，因此我们可以存储33,334个这些8位序列来表示1百万以下的哪些值是质数，因为我们涵盖了k可能具有的所有值，而不会超过1百万的限制。

- Michael Madsen

Answer 2

您不需要存储每个k的值。如果要存储100万以下的质数，请使用33,334字节-第一个字节对应于k = 0，第二个字节对应于k = 1等等。然后，在每个字节中，使用1位来指示30k + 1、30k + 7等数字是“质数”还是“合数”。

- user200783

Answer 3

这是一个位掩码，每个30个数字中的8个可能是质数，因此每30个数字需要8位。要制表所有小于10^6的质数，因此需要8 * 10 ^ 6/30 = 2666667位= 33334字节。

要解释为什么这是一种好方法，您需要查看明显的替代方案。

更加天真的方法只是使用位掩码。您需要100万位，125000字节。

您还可以存储质数本身的值。在1000000以下，值适合20位，有78498个质数，因此这给出了令人失望的1569960位（196245字节）。

另一种方法-虽然对查找质数不太有用-是存储每个质数与下一个质数之间的差异。在一百万以下，这适合6位（只要记住那时所有质数都是奇数，因此只需要存储偶数差异，因此可以丢弃最低位），共470998位== 58874字节。（通过计算必须跳过多少mod-30插槽，您可以刮掉另一个位。）

现在，30没有什么特别之处，除了30 = 2 * 3 * 5之外，因此在刚开始后，此查找实际上正在沿着Eratosthanes筛选模式的位掩码表示向上行走。相反，您可以使用2 * 3 * 5 * 7 = 210，然后您必须考虑+-1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103，共48个值。如果您使用了30个块中的7个进行此操作，则需要7 * 8 = 56位，因此这是一个轻微的改进，但很烦人。

因此，这是其中一种更好的技巧，用于紧凑地存储相对较小的质数。

（附言：有趣的是要注意，如果质数出现随机（但是同样数量的质数出现在1000000以下），则在1到10 ^ 6之间的数字的素性中存储的信息量为〜0.397位每个数字。因此，在天真的信息理论假设下，您会认为存储前一百万个质数的最佳方法可能是使用1000000 * 0.397位，或49609字节。）

- Rex Kerr

---

@Rex Kerr：感谢您的比较。这让事情变得更加清晰。不过有一件事：您是如何得出“每个数字约0.397位”的数字的？ - Lazer

p(prime) ~= 0.0785 是因为在前100万个数字中有78.5k个质数。以比特为单位的熵的公式是H = sum(-plog2(p)); 我们已经有了p(prime)和p(not prime)=1-p(prime)。代入：-0.0785log2(0.0785) - 0.9215*log2(0.9215) = 0.288 + 0.109 = 0.397 - Rex Kerr

Answer 4

从另一个角度来看，前23,163,298个质数可以被认为是很好的可压缩的。这是最大的质数数量，其中每个间隔都小于等于255，即适合单字节。

我在这里使用了这个事实，将质数缓存的内存占用减少了8倍，即不再使用number（8个字节），而是仅缓存质数之间的间隔，每个质数只使用1个字节。

- vitaly-t