Как я могу оптимизировать сито эратосфенов, чтобы просто хранить простые числа для очень большого диапазона?

Question

Я изучил работу Сито из Eratosthenes для генерации простых чисел до заданного числа с использованием итерации и удаления всех составных чисел. А алгоритм требует только повторения до sqrt (n), где n - верхняя граница, до которой нам нужно найти все простые числа. Мы знаем, что число простых чисел до n = 10^9 очень мало по сравнению с количеством составных чисел. Поэтому мы используем все пространство, чтобы просто сказать, что эти цифры не являются первыми, маркируя их составными. Мой вопрос в том, можем ли мы изменить алгоритм, чтобы просто хранить простые числа, так как мы имеем дело с очень большим диапазоном (поскольку число простых чисел очень меньше)? Можно ли просто сохранить простые числа?

Answer 1

Вы можете удалить каждое составное число из массива/вектора, как только вы продемонстрируете его составным. Или, когда вы заполняете массив чисел, чтобы пронести через сито, удалите все четные числа (кроме 2) и все числа, оканчивающиеся на 5.

Answer 2

Вы можете это сделать (удалите числа, которые, как обнаружено, не являются первичными из ваш массив/связанный список), но тогда временная сложность алгоритма будет деградировать до O (N^2/log (N)) или что-то вроде этого вместо оригинального O (N * log (N)). Это потому, что вы не сможете сказать, что «числа 2X, 3X, 4X, ...» больше не являются первичными. Вам придется перебирать весь сжатый список.

Answer 3

Если вы внимательно изучили сито, вы должны знать, что у нас нет простых чисел для начала. У нас есть array, sizeof которого равен диапазону. Теперь, если вы хотите, чтобы диапазон был 10e9, вы хотите, чтобы это был размер массива. Вы не упомянули ни одного языка, но для каждого номера вам необходимо указать bit, чтобы представить, является ли оно простым или нет.

Даже это означает, что вам нужно 10^9 bits = 1.125 * 10^8 байт, что превышает 100 МБ ОЗУ.

Если у вас есть все это, наиболее оптимизированная сито занимает O(n * log(log n)) время, которое, если n = 10e9, на машине, которая оценивает 10e8 инструкций в секунду, будет еще несколько минут.

Теперь, если у вас есть все это с вами, по-прежнему, количество простых чисел до 10e9 является q = 50,847,534, чтобы сохранить их будет еще q * 4 bytes, который до сих пор больше, чем 100MB. (больше ОЗУ)

Даже если вы удаляете индексы, кратные 2, 3 или 5, это удаляет 21 numbers in every 30. Это не достаточно хорошо, потому что в итоге вам все равно потребуется около 140 MB места. (40 МБ = третья часть 10^9 бит + ~ 100 МБ для хранения простых чисел).

Итак, поскольку для хранения простых чисел вы в любом случае потребуете такого же объема памяти (того же порядка, что и расчет), ваш вопрос, у ИМО нет решения.

---

Answer 4

Изменение структуры от этого набора (сито) - один бит на кандидат - для хранения простые числа (например, в виде списка, вектора или древовидной структуры) фактически повышает требования к хранению.

Пример: имеется 203.280.221 простых чисел ниже 2^32. Массив из uint32_t этого размера требует около 775 MiB, тогда как соответствующий битмап (a.k.a.set) занимает только 512 MiB (2^32 бит/8 бит/байт = 2^29 байтов).

Самое компактное цифровое представление с фиксированным размером ячейки будет хранить половинное расстояние между последовательными нечетными штрихами, так как примерно до 2^40 половинное расстояние вписывается в байты. В 193 MiB для простых чисел до 2^32 это немного меньше, чем бит-карта только для шансов, но эффективна только для последовательной обработки. Для просеивания это не подходит, потому что, как отметил Анатолий, алгоритмы, такие как Сито Эратосфена, эффективно требуют заданного представления.

Растровое изображение может быть резко сокращено, если оставить кратные мелкие простые числа. Наиболее известным является только однообразное представление, которое не учитывает число 2 и его кратность; это вдвое уменьшает потребность в пространстве до 256 мегабайт практически без дополнительной загрузки. Вам просто нужно помнить, что нужно вытащить номер 2 из тонкого воздуха, когда это необходимо, поскольку оно не представлено в сите.

Еще больше места можно сохранить, оставив кратные более мелкие простые числа; это обобщение трюка «только для шансов» обычно называется «колесным хранилищем» (см. Wheel Factorization в Википедии). Однако выигрыш от добавления более мелких простых чисел к колесу становится все меньше и меньше, тогда как модуль колес («окружность») взрывоопасен. Добавление 3 удаляет 1/3 оставшихся номеров, добавив 5 удалений еще 1/5, добавление 7 добавит вам еще 1/7 и так далее.

Вот краткий обзор того, что может добавить вас еще один штрих к колесу. 'ratio' - размер колесного/уменьшенного набора относительно полного набора, который представляет каждое число; «Дельта» дает усадку по сравнению с предыдущим шагом. «спицы» относятся к числу первичных спиц, которые должны быть представлены/сохранены; общее количество спиц для колеса, конечно, равно его модулю (окружность).

Мод 30 колеса (около 136 Мб для простых чисел до 2^32) предлагает отличное соотношение цена/польза, поскольку она имеет восемь прайм-несущих спиц, что означает, что имеется взаимно к-одному между колесами и 8-битными байтами. Это позволяет использовать многие эффективные трюки. Тем не менее, его стоимость при добавленной сложности кода значительна, несмотря на это случайное обстоятельство, и для многих целей только сито с коэффициентом («колесо мод 2») дает наибольшую выгоду для доллара.

Следует иметь в виду два дополнительных соображения. Во-первых, такие размеры данных, как эти, часто превышают емкость кэшей памяти с большой разницей, так что программы часто могут тратить много времени, ожидая, пока система памяти будет передавать данные. Это усугубляется типичными шаблонами доступа просеивания - шагами по всему диапазону снова и снова и снова. Ускорение на несколько порядков возможно за счет обработки данных небольшими партиями, которые вписываются в кеш-память уровня 1 процессора (обычно 32 KiB); меньшие ускорения все еще возможны, сохраняя вместимость кэшей L2 и L3 (несколько сотен KiB и несколько MiB соответственно). Ключевое слово здесь: 'сегментированное просеивание'.

Второе соображение заключается в том, что многие задачи просеивание - как знаменитый SPOJ PRIME1 и его обновленной версии PRINT (с расширенными границами и ужесточили ограничения по времени) - требуется только малый коэффициент воспламеняет до квадратного корня верхнего предела, чтобы быть постоянно доступный для прямого доступа. Это сравнительно небольшое число: 3512 при просеивании до 2^31, как в случае с PRINT.

Поскольку эти простые пробы уже просеяны, больше нет необходимости в представлении множества, и, поскольку их мало, проблем с пространством для хранения нет.Это означает, что они наиболее выгодно сохраняются как фактические числа в векторе или списке для легкой итерации, возможно, с дополнительными вспомогательными данными, такими как текущее смещение и фаза. Фактическая просеивающая задача затем легко выполняется с помощью метода под названием «просеивание окон». В случае PRIME1 и PRINT это может быть на несколько порядков быстрее, чем просеивание всего диапазона до верхнего предела, поскольку обе задачи требуют только небольшого количества поддиапазонов.

Answer 5

Вы можете уменьшить вдвое размер сита, только «сохраняя» нечетные числа. Это требует, чтобы код явно рассматривал случай тестирования четных чисел. Для нечетных чисел бит b сита представляет n = 2b + 3. Следовательно, бит 0 представляет 3, бит 1 представляет 5 и так далее. Существует небольшая накладная плата при преобразовании числа n и битового индекса b.

Независимо от того, какой метод вы используете, зависит от требуемого баланса памяти/скорости.