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

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, которые приятно хранить в байтах.

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

Answer 2

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

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

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

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

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

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

Answer 3

В настоящий момент вы рассматриваете 2 как особый случай, а затем имеете массив, в котором каждое нечетное число отображается в элемент массива (некоторые нечетные числа являются простыми). Вы можете улучшить это, рассматривая 2 и 3 как особые случаи, признавая, что остальные простые числа имеют вид 6n + 1 или 6n-1 (то есть для всех простых чисел p, где p & Gt; 3, p mod 6 = 1 или 5). Это можно обобщить подробнее - см. Википедию . Для всех простых чисел p & Gt; 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

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

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

& # 960; (L) / (L / ln (L)) приближается к 1.

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

Answer 6

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

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

Answer 7

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

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

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

Answer 8

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

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

Answer 9

Ознакомьтесь с руководством по topcoder по простым числам: http://community.topcoder.com/tc -модуль = Static амп &; d1 = учебники амп &; d2 = math_for_topcoders