这是一个位掩码,每个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字节。)