Virus neutralizer
Game: Perform tasks and rest cool.1 people play!
Play game
Привет, Вы узнаете о том , что такое решето аткина, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое
решето аткина , настоятельно рекомендую прочитать все из категории Стереометрия.
решето аткина — алгоритм нахождения всех простых чисел до заданного целого числа N. Алгоритм был создан А. О. Л. Аткином и Д. Ю. Бернштайном . Заявленная авторами асимптотическая скорость работы алгоритма соответствует скорости лучших ранее известных алгоритмов просеивания, но в сравнении с ними решето Аткина требует меньше памяти.
Описание
Основная идея алгоритма состоит в использовании неприводимых квадратичных форм (представление чисел в виде ax2 + by2). Предыдущие алгоритмы в основном представляли собой различные модификации решета Эратосфена, где использовалось представление чисел в виде редуцированных форм (как правило, в виде произведения xy).
В упрощенном виде алгоритм может быть представлен следующим образом:
- Все числа, равные (по модулю 60) 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56 или 58, делятся на 2 и поэтому заведомо не простые. Все числа, равные (по модулю 60) 3, 9, 15, 21, 27, 33, 39, 45, 51 или 57, делятся на 3 и тоже не являются простыми. Все числа, равные (по модулю 60) 5, 25, 35 или 55, делятся на 5 и также не простые. Все эти остатки (по модулю 60) игнорируются.
- Все числа, равные (по модулю 60) 1, 13, 17, 29, 37, 41, 49 или 53, имеют остаток от деления на 4, равный 1. Эти числа являются простыми тогда и только тогда, когда количество решений уравнения 4x2 + y2 = n нечетно и само число не кратно никакому квадрату простого числа (en:square-free integer).
- Числа, равные (по модулю 60) 7, 19, 31, или 43, имеют остаток от деления на 6, равный 1. Эти числа являются простыми тогда и только тогда, когда количество решений уравнения 3x2 + y2 = n нечетно и само число не кратно никакому квадрату простого.
- Числа, равные (по модулю 60) 11, 23, 47, или 59, имеют остаток от деления на 12, равный 11. Эти числа являются простыми тогда и только тогда, когда количество решений уравнения 3x2 − y2 = n (для x > y) нечетно и само число n не кратно никакому квадрату простого.
- Отдельный шаг алгоритма вычеркивает числа, кратные квадратам простых чисел. Об этом говорит сайт https://intellect.icu . Так как ни одно из рассматриваемых чисел не делится на 2, 3, или 5, то, соответственно, они не делятся и на их квадраты. Поэтому проверка, что число не кратно квадрату простого числа, не включает 22, 32, и 52.
Сегментация
Для уменьшения требований к памяти «просеивание» производится порциями (сегментами, блоками), размер которых составляет примерно
.
Предпросеивание
Virus neutralizer
Game: Perform tasks and rest cool.1 people play!
Play game
Для ускорения работы алгоритм игнорирует все числа, которые кратны одному из нескольких первых простых чисел (2, 3, 5, 7, …). Это делается путем использования стандартных структур данных и алгоритмов их обработки, предложенных ранее Полом Притчардом (англ. Paul Pritchard)
. Они известны под названием англ. wheel sieving. Количество первых простых чисел выбирается в зависимости от заданного числа
N. Теоретически предлагается брать первые простые примерно до

. Это позволяет улучшить асимптотическую оценку скорости алгоритма на множитель

. При этом требуется дополнительная память, которая с ростом
N ограничена как

. Увеличение требований к памяти оценивается как

.
Версия, представленная на сайте одного из авторов , оптимизирована для поиска всех простых чисел до миллиарда (
), в ней исключаются из вычислений числа, кратные 2, 3, 5 и 7 (2 × 3 × 5 × 7 = 210).
Оценка сложности
По оценке авторов , алгоритм имеет асимптотическую сложность
и требует
битов памяти. Ранее были известны алгоритмы столь же асимптотически быстрые, но требующие существенно больше памяти . Теоретически в данном алгоритме сочетается максимальная скорость работы при наименьших требованиях к памяти. Реализация алгоритма, выполненная одним из авторов, показывает достаточно высокую практическую скорость .
В алгоритме используется два вида оптимизации, которые существенно повышают его эффективность (по сравнению с упрощенной версией).
Virus neutralizer
Game: Perform tasks and rest cool.1 people play!
Play game
Ниже представлена реализация упрощенной версии на языке программирования C, иллюстрирующая основную идею алгоритма — использование квадратичных форм:
Версия алгоритма на языке Pasca
Вау!! 😲 Ты еще не читал? Это зря!
Исследование, описанное в статье про решето аткина, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое решето аткина
и для чего все это нужно, а если не понял, или есть замечания,
то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории
Стереометрия
Из статьи мы узнали кратко, но содержательно про решето аткина
Комментарии
Оставить комментарий
Стереометрия
Термины: Стереометрия