Решето Эратосфена и поиск простых чисел
Как найти все простые числа сразу — и сколько это стоит.
11 класс, углублённый уровень — пара пятнадцатая.
Уроки 29–30 поурочного плана: «Поиск простых чисел в заданном диапазоне с
помощью алгоритма „решето Эратосфена“» и практическая работа «Поиск простых
чисел в заданном диапазоне». На прошлой паре мы оценивали сложность
алгоритмов. Сегодня — алгоритм, которому больше двух тысяч лет, и он до сих
пор один из самых быстрых.
Простые числа
Простое число — натуральное число больше 1, у которого
ровно два делителя: 1 и само число. Остальные числа больше 1 — составные.
Число 1 — ни простое, ни составное: у него один
делитель.
2 — единственное чётное простое. Все остальные
чётные делятся на 2.
Простых чисел бесконечно много (Евклид), но чем дальше, тем реже они
встречаются: до 100 их 25, а среди чисел от 1 000 000 до 1 000 100 — всего 6.
Близнецы — простые p и p + 2: 3 и 5, 11 и 13, 17 и 19, 101 и 103.
Проверка делителями до √n
Чтобы узнать, простое ли n, не нужно делить на все числа до n − 1.
Если n = a·b и оба множителя больше √n, то a·b > n. Значит, у
составного n есть делитель d ≤ √n.
97: √97 ≈ 9,8. Проверяем 2, 3, 5, 7 — ни одно не
делит. 97 — простое.
91: √91 ≈ 9,5. 91 = 7·13 — делитель 7 ≤ 9,5 нашёлся.
Составное.
Так проверяют одно число. А если нужны все простые до миллиона?
Решето Эратосфена
- Выписываем числа от 2 до N.
- Первое невычеркнутое число p — простое.
- Вычёркиваем его кратные, начиная с p·p.
- Берём следующее невычеркнутое и повторяем, пока p·p ≤ N.
- Невычеркнутые — ровно простые.
Эратосфен Киренский, III век до н. э.: числа будто
просеивают — составные «проваливаются».
N = 50, вычеркнули кратные 2 и 3
ещё кратные 5 и 7 — готово: 7·7 = 49 ≤ 50 < 11·11
Почему с p·p и до √N
Начало — p·p
Кратные p меньше p·p — это p·k при k < p. У k есть простой делитель меньше
p, и это число уже вычеркнуто. Для 7: 14, 21, 28, 35, 42 вычеркнули 2, 3 и
5, первое новое — 49.
Конец — p·p > N
Если p·p > N, у шага p нечего вычеркнуть: всё, что меньше p·p, уже
вычеркнуто. Для N = 100 хватает 2, 3, 5, 7, ведь 11·11 = 121 > 100.
Кратные составного числа вычёркивать не нужно — их уже
вычеркнул его простой делитель. Но одно число может вычеркнуться и дважды:
12 — как кратное 2 и как кратное 3.
Частая ошибка: остановиться раньше времени. После кратных 2, 3
и 5 среди чисел до 100 ещё стоят 49, 77, 91 — кратные 7.
Решето в программе
Сколько раз выполнится 
? По строке на каждое p, где
внутренний цикл не пуст:
Число вычёркиваний на шаге p: ⌊(N − p·p)/p⌋ + 1. Для
p = 2: от 4 до 30 через 2 — 14 чисел.
не пускает
составные p, а для p ≥ 7 range уже пуст: 49 > 30.
Сколько стоит решето
Время
Шаг p вычёркивает около N/p чисел. Всего N/2 + N/3 + N/5 + N/7 + … — порядка
N·log log N: чуть больше N.
Память
По отметке на каждое число — порядка N. Это плата за скорость.
| N | решето: вычёркиваний | проверка каждого числа: делений до первого делителя |
|---|
| 10 000 | 16 981 | 117 527 |
| 100 000 | 193 078 | 2 745 694 |
Подсчитано прогоном. N выросло в 10 раз: решето — примерно в 11 раз,
проверка делителями — в 23 раза.
Без
программа вычёркивает и кратные
составных — ответ тот же, но работы больше. Начало с 2·p вместо p·p — тоже
лишняя работа: эти числа уже вычеркнуты.
Простые на отрезке — вручную
Нужны простые числа от 120 до 150. Решето от 2 не нужно: вычёркиваем числа
отрезка, кратные простым до √150 ≈ 12,2 — это 2, 3, 5, 7, 11.
Пишем отрезок по десяткам: кратные 2 и 5 — сразу целые
столбцы, кратные 3 — по сумме цифр.
Простые: 127, 131, 137, 139, 149 — их 5. Близнецы — 137
и 139. Не забыть 121 = 11·11 и 143 = 11·13: на 2, 3, 5, 7 они не делятся.
Решето на отрезке [A; B]
Когда отрезок далеко — например, от 1 000 000 до 1 000 100, — выписывать
числа от 2 незачем.
Берём простые p до √B и для каждого вычёркиваем на отрезке
его кратные. Начало — большее из двух: p·p и первое кратное p, не меньшее
A, то есть ⌈A/p⌉·p.
[1000; 1100], p = 13: 1000 / 13 ≈ 76,9 → 77·13 = 1001, а
13·13 = 169. Начало — 1001.
[100; 200], p = 13: ⌈100/13⌉·13 = 104, а 13·13 = 169.
Начало — 169: 104, 117, … уже вычеркнули меньшие простые.
После вычёркивания кратных 2, 3 и 5 картина повторяется
каждые 30 чисел: в каждых 30 подряд остаются ровно 8 — с остатками 1, 7, 11,
13, 17, 19, 23, 29.
Практическая работа: простые от A до B
Последний цикл меняем под вопрос:
| что спросили | что делаем с простым n |
|---|
| сколько | k = k + 1 |
| сумма | k = k + n |
| наибольшая разность соседних | n − предыдущее простое, берём наибольшее |
| близнецы | проверяем, простое ли n + 2 и не больше ли оно B |
| k-е по счёту | считаем и останавливаемся на k-м |
Проверь программу на маленьком отрезке, где ответ знаешь:
от 120 до 150 простых 5, сумма 683. Только потом ставь большие числа.
Что верно, а что нет
Верно
- У составного n есть делитель не больше √n.
- Вычёркивать кратные p можно с p·p.
- Хватает простых p, у которых p·p ≤ N.
- Решету нужна память порядка N.
Неверно
- «1 — простое». Делитель у него один.
- «Не делится на 2, 3, 5 — значит простое». 49 = 7·7.
- «Каждое число вычёркивается один раз». 12 — дважды.
- «Простые с ростом чисел встречаются чаще». Реже.
Что делаем дальше
- Обзорный практикум — шесть задач, все сразу на странице, в любом
порядке: понятия, решето вручную, сколько вычёркиваний сделает программа,
решето на отрезке, простые на отрезке вручную и программой.
- Отрезки — на черновике по десяткам, как на слайдах. Код в задачах —
картинкой, его читают.
- Шестой вопрос — практическая работа: свою программу пишем в IDLE.
- Ответ везде — целое число.
Отметка: закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Исправленная задача не
засчитывается — за ошибку приходит новая, добирать можно до пятёрки.
За работу
Практикум «Решето Эратосфена и поиск простых чисел» — в общей
папке и на сайте. Не успел на уроке — пройди дома: вариант будет другой, сдаётся
тем же кодом.
Карточку в тетрадь можно взять с собой: на ней решето, правило «с p·p и пока
p·p ≤ N», решето на отрезке и образец программы.
— список из N + 1 значений True:
s[n] значит «n ещё не вычеркнуто». 
— от p·p
до N с шагом p.