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

Question

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

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

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

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

Answer 1

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

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

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

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

Это объясняется более подробно здесь .

Answer 2

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

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

Для диапазонов от 1999066711391 и более, требуется больший размер ячейки или хранилище переменной длины. Последнее может быть чрезвычайно эффективным, даже если используются очень простые схемы (например, продолжайте добавлять до тех пор, пока не будет добавлен байт <255, как при сжатии в стиле <a href="http://en.wikipedia.org/wiki/LZ4_%28compression_algorithm%29"> LZ4 ), из-за чрезвычайно низкой частоты разрывов, превышающих 510 / 2.

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

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

Как насчет дерева интервалов? http://www.geeksforgeeks.org/interval-tree/

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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

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

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

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

Answer 9

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

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