Эффективно храня список простых чисел
В этой статье говорится:
Каждое простое число может быть выражено как
30k±1,30k±7,30k±11, или30k±13для некоторыхk. Это означает, что мы можем использовать восемь битов на тридцать чисел для хранения всех начал; миллион начал может быть сжат до 33 334 байтов
"Это означает, что мы можем использовать восемь битов на тридцать чисел для хранения всех начал"
Это "восемь битов на тридцать чисел" было бы для k, корректного? Но каждое значение k будет не обязательно натяжное устройство всего один бит. Разве это не должны быть восемь значений k вместо этого?
"миллион начал может быть сжат до 33 334 байтов"
Я не уверен, как это верно.
Мы должны указать на две вещи:
ЗНАЧЕНИЕ k (может быть произвольно большим),
СОСТОЯНИЕ от одного из восьми состояний
(-13,-11,-7,-1,1,7,11,13)
Я не следую, как "33 334 байта" прибылись, но я могу сказать одну вещь: поскольку простые числа становятся больше и больше в значении, нам будет нужно больше пространства для хранения значения k.
Как, затем мы можем зафиксировать его на уровне "33 334 байтов"?
3 ответа
Вам не нужно хранить каждое значение k. Если вы хотите хранить простые числа меньше 1 миллиона, используйте 33 334 байта - первый байт соответствует k=0, второй k=1 и т.д.. Затем в каждом байте используйте 1 бит для обозначения "простое" или "составное" для 30k+1, 30k+7 и т.д.
Это битовая маска - один бит для каждого из 8 значений из 30, которые могут быть простыми, так что 8 бит на 30 чисел. Чтобы табулировать все простые числа до 10^6, вам потребуется 8*10^6/30 = 2666667 бит = 33334 байта.
Чтобы объяснить, почему это хороший способ, нужно рассмотреть очевидные альтернативы.
Более наивным способом было бы просто использовать битовую маску. Вам нужен миллион битов, 125000 байт.
Можно также хранить значения самих простых чисел. До 1000000 значения укладываются в 20 бит, а простых чисел 78498, что дает неутешительные 1569960 бит (196245 байт).
Другой способ - хотя и менее полезный для поиска простых - хранить разницу между каждым простым и следующим. При миллионе это укладывается в 6 бит (если вы помните, что в этот момент все простые числа нечетные, поэтому вам нужно хранить только четные разности и вы можете отбросить младший бит), что составляет 470998 бит == 58874 байта. (Вы можете сэкономить еще один бит, подсчитав, сколько слотов mod-30 вам пришлось перепрыгнуть)
Теперь, в числе 30 нет ничего особенного, кроме того, что 30 = 2*3*5, так что этот поиск фактически проводит вас через битовую маску представления шаблона сита Эратосфена сразу после того, как вы начали. Вместо этого вы могли бы использовать 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 бит, так что это небольшое улучшение, но... вряд ли оно стоит таких хлопот.
Итак, это один из лучших трюков для компактного хранения достаточно маленьких простых чисел.
(P.S. Интересно отметить, что если бы простые числа появлялись случайным образом (но до 1000000 появлялось то же число, что и на самом деле), то количество информации, хранящейся в первичности числа от 1 до 10^6, составляло бы ~0.397 бит на число. Таким образом, при наивных информационно-теоретических предположениях можно подумать, что лучшее, что можно сделать для хранения первого миллиона простых чисел - это использовать 1000000*0.397 бит, или 49609 байт.)
.Статья немного вводит в заблуждение: мы не можем хранить 1 миллион простых чисел, но мы можем хранить все простые числа меньше 1 миллиона.
Значение k определяется его позицией в списке. Нам нужен только 1 бит для каждой из этих 8 перестановок (-13,-11...,11,13)
Другими словами, мы будем использовать 8 бит для хранения для k=0, 8 для хранения для k=1, 8 для хранения для k=2 и т. д. Позволяя им следовать последовательно, нам не нужно указывать значение k для каждых 8 бит - это просто значение для предыдущих 8 бит + 1.
Поскольку 1,000,000 / 30 = 33,333 1/3, мы можем хранить 33,334 таких 8-битных последовательностей, чтобы представить, какие значения ниже 1 миллиона являются простыми, поскольку мы охватываем все значения k, которые могут быть без 30k-13, превышающих предел в 1 миллион.