0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Теги: алгоритмы для разработчиков, решето эратосфена, вычислительная сложность алгоритма, метод от противного</p>
1
<p>Теги: алгоритмы для разработчиков, решето эратосфена, вычислительная сложность алгоритма, метод от противного</p>
2
<p>Что такое решето Эратосфена, знает сегодня, пожалуй, любой школьник, интересующийся математикой. Но не всякий знает, какова алгоритмическая сложность этого "просеивателя".</p>
2
<p>Что такое решето Эратосфена, знает сегодня, пожалуй, любой школьник, интересующийся математикой. Но не всякий знает, какова алгоритмическая сложность этого "просеивателя".</p>
3
<h2>Напомним условие задачи</h2>
3
<h2>Напомним условие задачи</h2>
4
<p>Необходимо найти все простые числа, меньшие или равные заданному числу<strong>N</strong>.</p>
4
<p>Необходимо найти все простые числа, меньшие или равные заданному числу<strong>N</strong>.</p>
5
<p>Запишем в ряд все числа<strong>от 1 до N</strong>и будем вычёркивать оттуда все числа, кратные двойке, но больше двойки, затем, все числа, кратные тройке, но больше тройки и т. д.</p>
5
<p>Запишем в ряд все числа<strong>от 1 до N</strong>и будем вычёркивать оттуда все числа, кратные двойке, но больше двойки, затем, все числа, кратные тройке, но больше тройки и т. д.</p>
6
<p>Если число уже вычеркнуто, пропускаем его и переходим к следующему. Так мы продолжаем, пока не дойдем до<strong>N</strong>. В итоге у нас останутся невычеркнутыми только простые числа.</p>
6
<p>Если число уже вычеркнуто, пропускаем его и переходим к следующему. Так мы продолжаем, пока не дойдем до<strong>N</strong>. В итоге у нас останутся невычеркнутыми только простые числа.</p>
7
<h2>Почему так?</h2>
7
<h2>Почему так?</h2>
8
<p>Потому что оставшиеся числа не делятся ни на что,<strong>кроме самих себя и единицы</strong>. Это легко доказать<strong>методом от противного</strong>. Допустим, осталось число n и оно делится на некоторое k, такое, что<strong>1 < k < n</strong>. Значит, оно должно было быть вычеркнуто, когда вычёркивали числа, делящиеся на k. А оно у нас не вычеркнулось.</p>
8
<p>Потому что оставшиеся числа не делятся ни на что,<strong>кроме самих себя и единицы</strong>. Это легко доказать<strong>методом от противного</strong>. Допустим, осталось число n и оно делится на некоторое k, такое, что<strong>1 < k < n</strong>. Значит, оно должно было быть вычеркнуто, когда вычёркивали числа, делящиеся на k. А оно у нас не вычеркнулось.</p>
9
<h2>Оптимизации</h2>
9
<h2>Оптимизации</h2>
10
<p>Можно просеивать только нечётные числа, ибо чётные - заведомо составные. Можно просеивать только числа до √N.</p>
10
<p>Можно просеивать только нечётные числа, ибо чётные - заведомо составные. Можно просеивать только числа до √N.</p>
11
<h4>Теперь оценим потребление памяти и вычислительную сложность этого алгоритма</h4>
11
<h4>Теперь оценим потребление памяти и вычислительную сложность этого алгоритма</h4>
12
<p>По памяти этот алгоритм требует O(N), потому что размер целевого массива N и никакой дополнительной памяти не используется.</p>
12
<p>По памяти этот алгоритм требует O(N), потому что размер целевого массива N и никакой дополнительной памяти не используется.</p>
13
<p>Оценим теперь его вычислительную сложность (интересно, что<strong>оптимизации на асимптотическую сложность не влияют</strong>, а уменьшают только коэффициент). Для каждого простого p вычёркиваем числа N / p раз. Общее число действий, которые мы производим, равно сумме: Примем как данность, что число простых чисел, меньших либо равных N, приблизительно равно N / ln N, следовательно, k-e простое число приблизительно равно k ln k.</p>
13
<p>Оценим теперь его вычислительную сложность (интересно, что<strong>оптимизации на асимптотическую сложность не влияют</strong>, а уменьшают только коэффициент). Для каждого простого p вычёркиваем числа N / p раз. Общее число действий, которые мы производим, равно сумме: Примем как данность, что число простых чисел, меньших либо равных N, приблизительно равно N / ln N, следовательно, k-e простое число приблизительно равно k ln k.</p>
14
<p>Оценим сумму:</p>
14
<p>Оценим сумму:</p>
15
<p>Оценим новую сумму как интеграл:</p>
15
<p>Оценим новую сумму как интеграл:</p>
16
<p>Интересно,<strong>знал ли об этом Эратосфен</strong>?</p>
16
<p>Интересно,<strong>знал ли об этом Эратосфен</strong>?</p>
17
17