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

Question

Для библиотеки мне нужно сохранить первые числа простых чисел до предела L. Эта коллекция должна иметь время поиска O (1) (чтобы проверить, является ли число простым или нет), и оно должно быть легким, учитывая число, чтобы найти следующее простое число (при условии, что оно меньше L).

Учитывая, что L фиксирован, сито Eratostene для создания списка в порядке. Прямо сейчас я использую упакованный булевский массив для хранения списка, который содержит только записи для нечетных чисел между 3 и L (включительно). Это занимает (L-2)/2 бит памяти. Я хотел бы иметь возможность статически увеличивать L, не используя больше памяти.

Есть ли структура данных, использующая меньше памяти с аналогичными свойствами? Или, по крайней мере, с постоянным временем поиска? (Нечетные числа могут быть перечислены, пока мы не получим простые)

(язык я писал в это Factor, но этот вопрос будет таким же на любом языке, который имеет встроенный или легко программируемые упакованные битовые массивы)

Answer 1

Вы можете явно проверить большее количество простых чисел, чтобы удалить избыточность.

В данный момент вы делаете это только на двоих, проверяя на делимость на два явно, а затем сохраняя только для нечетных чисел, являются ли они первыми.

Для 2 и 3 вы получаете остатки от 0 до 5, из которых только 1 и 5 не делятся на два или три и могут приводить к простому числу, поэтому вы сокращаетесь до 1/3.

Для 2, 3 и 5 вы получаете 8 номеров из 30, что приятно хранить в байте.

Подробнее об этом here.

Answer 2

Если вы можете определить, какие из них Mersenne или другие легко представленные простые числа, вы можете сохранить несколько бит, используя это представление с флагом для применимых номеров.

Кроме того, как насчет хранения чисел в качестве отличия от предыдущего номера? Тогда размер не должен расти так же быстро (но поиск будет медленным). Объединяясь с вышеприведенным подходом, вы можете сохранить простые числа Мерсенна и разницу между последней точкой Мерсена.

Answer 3

Учитывая, что память настолько дешевая, я не думаю, что вы можете сделать гораздо лучше с точки зрения скорости, чем ваша существующая схема.

Если есть лучшее решение, то я предполагаю, что бы воспользоваться Prime Number Theorem, который показывает, что, как L становится больше, предел

я (L)/(L/п (L)) приближается 1.

Возможно, лучшее решение будет иметь адаптивное решение для упаковки в структуре данных вроде как skip list.

Answer 4

Возможно, структура данных, содержащая только простые числа, - это то, что вы ищете. Вместо использования символов в качестве индексов вы можете использовать целые цифры. Реализация этого - Judy-Array с.

Да, они не соответствуют вашим требованиям O (1), они очень эффективны для работы с подобными ключами (как и большинство частей) и довольно быстро выглядят с помощью O (m) (m = key - длина) максимум.

Если вы ищете штрих в предварительно сгенерированном дереве, вы можете пройти дерево до тех пор, пока не найдете его, или вы уже находитесь на узле, который находится рядом с предыдущим и следующим простым.

Answer 5

В данный момент вы обрабатываете 2 как частный случай, а затем имеете массив, в котором каждое нечетное число сопоставляется с элементом в массиве (с некоторыми нечетными числами, являющимися начальными). Вы могли бы улучшить это, рассматривая 2 и 3 как особые случаи, признающие, что остальные простые числа имеют вид 6n + 1 или 6n-1 (то есть для всех простых чисел p, где p> 3, p mod 6 = 1 или 5). Это может быть дополнительно обобщено - см. Wikipedia. Для всех простых чисел p> 5, p mod 30 = 1, 7, 11, 13, 17, 19, 23 или 29. Вы можете продолжать использовать это и уменьшать объем памяти, необходимый за счет времени обработки (хотя это все равно будет O (1), только медленнее O (1)).

Answer 6

Как насчет какой-либо хеш-таблицы?

Вы должны были бы очень хорошая хеш-функции (что-то вроде n mod p, где p не кратна любого из q низших простых чисел - выбрать q достаточно высокой для того, чтобы свести к минимуму число столкновений).

Answer 7

Альтернатива упакованным растровым изображениям и колесам - но одинаково эффективная в определенных контекстах - это сохранение различий между последовательными штрихами. Если вы оставите номер 2, как обычно, все различия будут четными. Сохраняя разницу/2, вы можете получить до 2^40ish областей (как раз перед 1999066711391) с использованием байтовых переменных.

Пробуждение до 2^32 требует только 194 Мбайт, по сравнению с 256 Мбайт для только растрового изображения с коэффициентом. Итерация по дельта-хранимым числам намного быстрее, чем для колесного хранилища, которое включает в себя колесо modulo-2, известное как растровое изображение только для коэффициентов.

Для диапазонов от 1999066711391 и выше требуется больший размер ячейки или хранилище переменной длины. Последнее может быть чрезвычайно эффективным, даже если используются очень простые схемы (например, продолжать добавлять до тех пор, пока не будет добавлен байт < 255, как в случае сжатия LZ4) из-за чрезвычайно низкой частоты зазоров, превышающих 510/2.

Для эффективности лучше всего разделить диапазон на разделы (страницы) и управлять ими. Стиль B-Tree.

Энтропийное кодирование различий (Huffmann или арифметическое кодирование) сокращает требования к постоянному хранению чуть меньше половины, что близко к теоретическому оптимуму и лучше, чем списки или диски, сжатые с использованием лучших доступных упаковщиков.

Если данные хранятся несжатыми, то они по-прежнему намного компактнее, чем файлы двоичных или текстовых номеров, на порядок или больше. Благодаря индексу стиля B-Tree легко просто отображать разделы в памяти по мере необходимости и перебирать их с невероятной скоростью.

Answer 8

Проверьте TopCoder учебник по простым числам: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders

Answer 9

Как насчет Interval Tree? http://www.geeksforgeeks.org/interval-tree/

Возможно, это не O (1), но это очень быстро. Например, O (log (p (n))), где p (n) - число простых чисел до числа n. Таким образом, вам понадобится память, которая будет пропорциональна количеству простых чисел, что значительно сократит стоимость памяти.

Например, предположим, что вы находите штрих в точке p1, а затем следующий в p2, . Вставьте интервал (p1, p2) и т. Д., И когда вы запустите поиск любого числа в этом диапазоне, он вернет этот интервал и вы можете вернуть p2, который будет ответом в вашем случае.