Эффективное хранение списка простых чисел

Question

В этой статье говорится:

Каждое простое число может быть выражено как 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 байта" было получено , но могу сказать одно: по мере того, как простые числа становятся все больше и больше по значению, нам потребуется больше места для хранения значения * * к тысяче сорок-девять .

Как, тогда мы можем исправить это в "33,334 байт"?

Answer 1

Эта статья немного вводит в заблуждение: мы не можем хранить 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 млн.

Answer 2

Вам не нужно хранить каждое значение k. Если вы хотите сохранить простые числа менее 1 миллиона, используйте 33,334 байта - первый байт соответствует k = 0, второй - k = 1 и т. Д. Затем в каждом байте используйте 1 бит для обозначения «простого» или «составного» "за 30к + 1, 30к + 7 и т. д.

Answer 3

Это битовая маска - один бит для каждого из 8 значений из 30, которые могут быть простыми, поэтому 8 бит на 30 чисел. Таким образом, для суммирования всех простых чисел до 10 ^ 6 необходимо 8 * 10 ^ 6/30 = 2666667 бит = 33334 байта.

Чтобы объяснить, почему это хороший путь, вам нужно взглянуть на очевидные альтернативы.

Более наивным способом было бы просто использовать битовую маску. Вам нужен миллион бит, 125000 байт.

Вы также можете хранить значения простых чисел. До 1000000 значения умещаются в 20 битов, а число простых чисел составляет 78498, что дает разочаровывающие 1569960 бит (196245 байт).

Еще один способ - хотя и менее полезный для поиска простых чисел - это сохранить различия между каждым простым и следующим. Менее миллиона это соответствует 6 битам (если вы помните, что в этой точке все нечетные простые числа, поэтому вам нужно хранить только четные различия и, следовательно, отбрасывать младший бит), для 470998 бит == 58874 байта , (Вы можете сбрить еще один бит, посчитав, сколько слотов мод-30 вам пришлось прыгнуть.)

Теперь, нет ничего особенно особенного в 30, кроме 30 = 2 * 3 * 5, так что этот поиск на самом деле проведет вас через представление битовой маски шаблона Sieve of 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 бит, так что это небольшое улучшение, но тьфу ... вряд ли стоило хлопот.

Так что это один из лучших приемов компактного хранения достаточно малых простых чисел.

(PS Интересно отметить, что если бы простые числа появлялись случайным образом (но то же самое число появлялось до 1000000, как на самом деле появляются), то объем информации, хранимой в простоте числа между 1 и 10 ^ 6, составлял бы ~ 0.397 бит на Таким образом, при наивных теоретико-информационных допущениях вы могли бы подумать, что лучшее, что вы могли бы сделать для хранения первого миллиона простых чисел, это использовать 1000000 * 0,397 бит или 49609 байт.)