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

Математика, 5 класс. Учебник: Алдамуратова Т.А. и др. (Атамұра, 2017). Глава II: Делимость натуральных чисел. Страницы 77.

Коротко о главном

Самого большого простого нет

Ещё в III веке до нашей эры древнегреческий математик Евклид доказал: простых чисел бесконечно много. Сколько бы ты их ни нашёл, всегда найдётся ещё одно, больше.

Но как быстро найти все простые числа, скажем, до 50? Не проверять же каждое делением!

Дощечка с дырочками

Чуть позже в египетском городе Александрия жил математик Эратосфен. Он писал числа на дощечке, покрытой воском, и прокалывал палочкой единицу и все составные числа. Дощечка становилась похожей на решето — сито для муки. А в нём «застревали» только простые числа.

Так и появилось название — решето Эратосфена.

🌟 Эратосфен был не только математиком. Он первым довольно точно измерил размер Земли — по тени от палки в двух разных городах!

Как просеивать

1. Выпиши числа подряд. Единицу сразу вычеркни — она не простая.
2. Первое невычеркнутое число — 2. Обведи его, а все числа, кратные 2 (4, 6, 8…), вычеркни.
3. Следующее невычеркнутое — 3. Обведи и вычеркни кратные 3: 9, 15, 21… (чётные уже вычеркнуты).
4. Дальше 5: обведи и вычеркни 25, 35, 45…
5. Потом 7: из его кратных невычеркнутым осталось только 49.
6. Следующее простое 11, а $11 \cdot 11 = 121$ — это уже за границей таблицы. Стоп! Всё, что не вычеркнуто, — простые числа.

💡 Остановиться можно, когда квадрат очередного обведённого числа больше границы таблицы. Для таблицы до 50 хватает просеять кратные 2, 3, 5 и 7.

Просей сам!

Представь, что ты Эратосфен. Мысленно вычеркни кратные 2, 3, 5, 7 и отметь числа, которые «застряли» в решете.

⚠️ Частая ошибка. Отмечают 49 или 21 и 27 — «они же нечётные». Но $49 = 7 \cdot 7$, $21 = 3 \cdot 7$, $27 = 3 \cdot 9$. Нечётное — ещё не значит простое.

👨‍👩‍👧 Родителю. Хорошее домашнее занятие на 15 минут: начертите таблицу от 1 до 100 (10 строк по 10 чисел), и пусть ребёнок «просеет» её разными цветами — кратные 2 одним цветом, кратные 3 другим и так далее. Должно остаться 25 простых чисел. Заодно станет видно, что кратные 2 и 5 стоят ровными столбиками, а кратные 3 идут по диагоналям.

Решаем упражнения

Простыми числами занимались и много веков спустя. Русский математик П. Л. Чебышев (1821–1894) доказал: между любым числом больше 1 и числом вдвое больше него всегда есть хотя бы одно простое. Например, между 5 и 10 есть 7, а между 17 и 34 — целых четыре: 19, 23, 29, 31. Много нового о простых числах открыл и И. М. Виноградов (1891–1983).

Задание 1

С помощью решета Эратосфена составь таблицу простых чисел: а) от 1 до 20; б) от 1 до 50.

Как думать. Просеиваем, как Эратосфен. Для 20 хватит кратных 2 и 3 ($5 \cdot 5 = 25 > 20$). Для 50 — кратных 2, 3, 5 и 7.

Решение. а) Выписываем 1–20, вычёркиваем 1, затем кратные 2 (кроме 2) и кратные 3 (кроме 3). Кратные 5 уже вычеркнуты: 10, 15, 20 делятся на 2 или 3. Остаются 2, 3, 5, 7, 11, 13, 17, 19. б) Выписываем 1–50 и вычёркиваем 1, кратные 2, 3, 5, 7 (кроме самих этих чисел). Из кратных 7 ещё не вычеркнуто только 49. Дальше можно не идти: $11 \cdot 11 = 121 > 50$.

Ответ: а) 2, 3, 5, 7, 11, 13, 17, 19 (8 чисел); б) 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 (15 чисел).

Задание 2

Напиши простые числа: а) между 13 и 26; б) между 9 и 18.

Как думать. Это как раз примеры к теореме Чебышева: $26 = 2 \cdot 13$, $18 = 2 \cdot 9$. Сами 13 и 9 в ответ не входят — нужны числа «между».

Решение. Берём таблицу из задания 1. а) Между 13 и 26: 17, 19, 23. б) Между 9 и 18: 11, 13, 17.

Ответ: а) 17, 19, 23; б) 11, 13, 17.