This article的名单说：有效地存储素数
每一个素数可以表示为
30k±1，30k±7，30k±11，或30k±13一些k。 这意味着我们可以使用每个 的三位数字来存储所有的素数;一百万素数可 压缩到33,334字节
“这意味着我们可以使用每个30号八位来存储所有的素数”
这种“每八位30号”将为k，对吗？但是每个值不一定只占用一位。不应该是八个k值而不是？
“百万素可以压缩到33,334字节”
我不知道如何这是真的。
我们需要指出两点：
的k值（可以任意大）
从八个州的一个状态(-13,-11,-7,-1,1,7,11,13)
我不遵循如何“33,334字节”到达，但我可以说一件事：随着素数越来越大，价值较大，我们将需要更多空间来存储价值k。
那么，我们可以将它修复为“33,334字节”吗？
您不需要存储k的每个值。如果要将素数存储在100万以下，请使用33,334字节 - 第一个字节对应于k = 0，第二个对应k = 1等。然后，在每个字节中，使用1位来表示“素数”或“合成“对于30k + 1,3k + 7等。
这篇文章有点误导我们：我们不能存储100万个素数，但我们可以存储100万以下的所有素数。
k的值来自它在列表中的位置。我们只需要8位置换中的每一位（-13，-11 ...，11,13）
换句话说，我们将使用8位来存储k = 0,8来存储k = 1,8，以存储k = 2等。通过顺序地进行这些操作，我们不需要为每8位指定k的值 - 它仅仅是前8位+1的值。
由于1,000,000/30 = 33,333 1/3，我们可以存储33,334这8位序列，表示哪些值低于100万是素数，因为我们覆盖了所有k值可以不超过30k-13的值100万。
这是一个位掩码 - 对于30个可能为素数的8个值中的每一个，都有一位，所以每30个数字有8位。要将所有素数列表为10^6，您需要8 * 10^6/30 = 2666667位= 33334个字节。
为了解释为什么这是一个好方法，你需要看看明显的选择。
一个更幼稚的方法就是使用位掩码。你需要一百万位，125000字节。
你也可以存储素数的值。高达1000000，这些值适合20位，并且有78498个素数，所以这给出令人失望的1569960位（196245字节）。
另一种方法 - 尽管查找素数不太有用 - 但是要存储每个素数和下一个素数之间的差异。低于一百万，这符合6位（只要您记得那时素数都是奇数，所以您只需要存储偶数差异并因此可以丢掉最低位），即470998位== 58874字节。 （你可以通过计算你需要跳转多少个mod-30插槽来削减另外一点）。
现在，除了30 = 2 * 3 * 5之外，没有什么特别的30，所以这个查找实际上是在走你在开始之后立即通过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个值。如果你用7块30块这样做，你需要7×8 = 56位，所以这是一个小小的改进，但呃...几乎没有值得的麻烦。
所以这是更好的技巧之一，用于紧凑地存储合理的小素数。有趣的是，如果素数随机出现（但实际出现的相同数字达到1000000），则存储在1和10^6之间数字的素数中的信息量将是〜0.397比特因此，在天真的信息理论假设下，你会认为存储第一百万个素数的最好方法是使用1000000 * 0.397位或49609字节。）
@Rex Kerr：谢谢你的比较。这使事情变得更加清晰。但是有一件事：你是如何达到每个数字“〜0.397位”的？ – Lazer 2010-04-12 08:44:42
p（prime）〜= 0.0785，因为第一个1M数字中有78.5k素数。熵的公式为H = sum（-p * log2（p））;我们有p（素数）和p（不是素数）= 1-p（素数）。插入：-0.0785 * log2（0.0785） - 0.9215 * log2（0.9215）= 0.288 + 0.109 = 0.397 – 2010-04-12 09:27:23
应该是“每一个除了2,3和5之外的素数可以表示为...“？ – MatrixFrog 2010-04-10 17:00:35
@MatrixFrog：当然，但是你的“解压程序”只会在输出压缩数据之前输出这3个数据。 – 2010-04-10 18:54:05