Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Решето только по нечётным числам





Решето Эратосфена

Решето Эратосфена — это алгоритм, позволяющий найти все простые числа в отрезке за операций.

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

Реализация

Сразу приведём реализацию алгоритма:

int n;vector<char> prime (n+1, true);prime[0] = prime[1] = false;for (int i=2; i<=n; ++i) if (prime[i]) if (i * 1ll * i <= n) for (int j=i*i; j<=n; j+=i) prime[j] = false;

Этот код сначала помечает все числа, кроме нуля и единицы, как простые, а затем начинает процесс отсеивания составных чисел. Для этого мы перебираем в цикле все числа от до , и, если текущее число простое, то помечаем все числа, кратные ему, как составные.

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

При такой реализации алгоритм потребляет памяти (что очевидно) и выполняет действий (это доказывается в следующем разделе).

Асимптотика

Докажем, что асимптотика алгоритма равна .

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

Вспомним здесь два известных факта: что число простых, меньше либо равных , приблизительно равно , и что -ое простое число приблизительно равно (это следует из первого утверждения). Тогда сумму можно записать таким образом:

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

Теперь оценим такую сумму с помощью интеграла от той же функции по от до (мы можем производить такое приближение, поскольку, фактически, сумма относится к интегралу как его приближение по формуле прямоугольников):



Первообразная для подынтегральной функции есть . Выполняя подстановку и убирая члены меньшего порядка, получаем:

Теперь, возвращаясь к первоначальной сумме, получаем её приближённую оценку:

что и требовалось доказать.

Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright "An Introduction to the Theory of Numbers" (стр. 349).

Различные оптимизации решета Эратосфена

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

Кроме того, для достаточно больших узким местом становится объём потребляемой памяти.

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

Просеивание простыми до корня

Самый очевидный момент — что для того, чтобы найти все простые до , достаточно выполнить просеивание только простыми, не превосходящими корня из .

Таким образом, изменится внешний цикл алгоритма (укажите, как именно)

На асимптотику такая оптимизация не влияет (действительно, повторив приведённое выше доказательство, мы получим оценку , что, по свойствам логарифма, асимптотически есть то же самое), хотя число операций заметно уменьшится.

Решето только по нечётным числам

Поскольку все чётные числа, кроме , — составные, то можно вообще не обрабатывать никак чётные числа, а оперировать только нечётными числами.

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





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:



©2015- 2021 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.