Laz*_*zer 9 compression algorithm primes storage
这篇文章说:
每一个素数可以表示为
30k±1,30k±7,30k±11,或30k±13一些k.这意味着我们可以使用每30位数8位来存储所有素数; 一百万个素数可以压缩到33,334个字节
"这意味着我们可以使用每30位数8位来存储所有素数"
这个"每三十个八位"将用于k,对吗？但是每个k值不一定只占用一位.不应该是8 k值吗？
"一百万个素数可以压缩到33,334字节"
我不确定这是怎么回事.
我们需要指出两件事:
k的值(可以任意大)
状态来自八个州之一 (-13,-11,-7,-1,1,7,11,13)
我没有遵循"33,334字节"是如何得出的,但我可以说一件事:随着素数值变得越来越大,我们将需要更多的空间来存储k的值.
那怎么样,我们可以修复它"33,334字节"？
Mic*_*sen 16
这篇文章有点误导:我们不能存储100万个素数,但我们可以存储100万以下的所有素数.
k的值来自它在列表中的位置.对于这8个排列中的每一个,我们只需要1位(-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,我们可以存储这些8位序列中的33,334来表示低于100万的值是素数,因为我们覆盖了k可以拥有的所有值,而没有30k-13超过100万的限制.
use*_*783 11
您不需要存储k的每个值.如果要存储低于1百万的素数,请使用33,334字节 - 第一个字节对应于k = 0,第二个字节对应于k = 1等.然后,在每个字节中,使用1位表示"素数"或"复合" "为30k + 1,30k + 7等