Решето Эратосфена (уменьшение пространства сложности)

Question

Я хотел, чтобы генерировать простые числа между двумя заданными числами «а» и «B» (Ь> а). То, что я сделал, это хранить булевы значения в массиве размером b-1 (то есть для чисел до b), а затем я применил метод сита.

Есть ли лучший способ, который уменьшает сложность пространства, если мне не нужно все простые числа от 2 к б?

Answer 1

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

Answer 2

Вы можете использовать сегментированное сито Eratosthenes. Основная идея довольно проста.

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

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

Для сегментированного сита мы делаем все по-другому. Начнем с того, что мы находим только простые числа до квадратного корня из предела, о котором мы заботимся. Затем мы используем их для выделения простых чисел в основном массиве. Разница здесь заказ, в котором мы отмечаем простые числа. Вместо того, чтобы маркировать все кратные три, затем все кратные 5 и т. Д., Мы начинаем с выделения кратных трех для данных, которые будут вписываться в кеш. Затем, вместо продолжения большего количества данных в массиве, мы возвращаемся и отмечаем кратные пять для данных, которые вписываются в кеш. Тогда кратные 7 и т. Д.

Затем, когда мы отметили все кратные части данных размером в кеш-кеш, мы переходим к следующему фрагменту данных размером в кеш. Мы начинаем с выделения кратных 3 в этом фрагменте, затем кратных 5 и т. Д., Пока мы не отметим все кратные в этом фрагменте. Мы продолжаем эту модель до тех пор, пока мы не отметим все не-простые числа во всех кусках, и мы закончили.

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

Точное ускорение, которое дает это, будет зависеть от соотношения скорости кеша со скоростью основной памяти, размера используемого массива и размера кеша и т. Д. Тем не менее, он, как правило, довольно существенный - например, на моей конкретной машине, ища простые до 100 миллионов, сегментированное сито имеет преимущество в скорости около 10: 1.

Одна вещь, которую вы должны помнить, если вы используете C++.Хорошо известная проблема с std::vector<bool> - это под C++ 98/03, vector<bool> должен был быть специализацией, которая хранит каждый логический элемент как один бит с некоторой прокси-трюкой, чтобы получить поведение типа bool. С тех пор это требование было отменено, но многие библиотеки все еще включают его.

С несегментированным ситом, это, как правило, полезный компромисс. Хотя для вычисления масок требуется немного дополнительного времени процессора, и для изменения только одного бита за раз, он экономит достаточную полосу пропускания для основной памяти, чтобы компенсировать больше.

С сегментированным ситом пропускная способность для основной памяти не так велика, поэтому использование vector<char>, как правило, дает лучшие результаты (по крайней мере, с компиляторами и процессорами, которые мне удобны).

Для получения оптимальной производительности от сегментированного сита требуется знание размера кеша процессора, но получение его правильной точности обычно не является критическим - если вы предполагаете, что размер меньше, чем есть на самом деле, вы не будете обязательно получите оптимальное использование вашего кеша, но вы, как правило, тоже не потеряете много.