Решето Эратосфена и поиск простых чисел
11 класс, углублённый уровень. Обзорный практикум к пятнадцатой паре: шесть задач — решето на бумаге и в программе, простые числа на отрезке вручную и своей программой.
- Что нужно сделать
- Шесть задач — по одной на каждый вопрос темы, и все сразу на странице: решай в любом порядке. Ответил верно — вопрос закрыт. Ошибся — сразу видно, как это решается, а вопрос остаётся открытым: кнопка «Новые числа» даёт ту же задачу с другими данными. Времени нужно минут тридцать: числа отрезка удобно выписывать на черновике по десяткам, как на слайдах.
- Программы — картинкой, последняя — своя
- Код в задачах нарисован картинкой: его читают, а не запускают. Шестой вопрос — практическая работа: отрезок в сотни тысяч чисел вручную не просеять, программу для него пишешь сам в IDLE — решетом или проверкой делителей до √n. Образец — в «Подсказке».
- Отметка
- Закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Исправленная задача не засчитывается — за ошибку приходит новая, без ограничений: добирать можно до пятёрки. Кнопка «Получить код» появляется, как только закрыто три вопроса.
- Короткий ответ — знак в знак
- Ответ везде — целое число:
25, а не25 чисел. На КЕГЭ ответ читает машина, и здесь так же. - Как сдать
- В конце появится код работы и кнопка «Сдать работу»: впишешь код ученика, кнопка сама откроет форму с уже вписанным кодом. Переписывать код руками не надо — на этом чаще всего и ошибаются.
- Не успел на уроке
- Открой эту же страницу дома и пройди целиком: вариант будет другой, а сдаётся всё так же — одним кодом.
Вопросы темы
Подсказка: решето Эратосфена и поиск простых чисел
Простые числа
Простое число — натуральное число больше 1, у которого ровно два делителя: 1 и само число. Остальные числа больше 1 — составные. Число 1 ни простое, ни составное. 2 — единственное чётное простое. Простых чисел бесконечно много (Евклид), но с ростом чисел они встречаются всё реже. Близнецы — простые p и p + 2: 11 и 13, 17 и 19.
Проверка делителями до √n
Если n = a·b и оба множителя больше √n, то a·b > n. Значит, у составного n есть делитель d, для которого 1 < d ≤ √n, и проверять делители дальше √n не нужно: у 97 хватит 2, 3, 5, 7 (11·11 = 121 > 97).
Решето Эратосфена
Выписываем числа от 2 до N. Берём первое невычеркнутое число p — оно простое — и вычёркиваем его кратные. Переходим к следующему невычеркнутому, и так далее. Невычеркнутые в конце — ровно простые.
- Кратные p начинаем вычёркивать с p·p: у меньших кратных p·k (k < p) есть меньший простой делитель, и они уже вычеркнуты.
- Останавливаемся, когда p·p > N: такой шаг уже ничего не вычеркнет. Для N = 100 хватает 2, 3, 5, 7.
- Кратные составного не вычёркиваем — их уже вычеркнул его простой делитель. Одно число может вычеркнуться несколько раз: 12 — и как кратное 2, и как кратное 3.
Сколько стоит решето
Шаг p вычёркивает около N/p чисел: от p·p до N с шагом p — это ⌊(N − p·p)/p⌋ + 1 вычёркиваний. Всего N/2 + N/3 + N/5 + … — порядка N·log log N, чуть больше N. Память — порядка N: по отметке на каждое число. Проверка каждого числа делителями до √n — до N·√N действий: для N = 100 000 это 2,7 млн делений против 193 тыс. вычёркиваний решета. Решето быстрее во много раз, но платит памятью.
Простые на отрезке [A; B]
Нужны простые p до √B. Для каждого вычёркиваем числа отрезка, кратные p, начиная с большего из двух: p·p и первого кратного p, не меньшего A (это ⌈A/p⌉·p). Числа, не делящиеся на 2, 3 и 5, повторяются с периодом 30: в каждых 30 подряд их ровно 8.
Программа: простые от A до B
Для отрезка до нескольких миллионов решето работает секунды. Можно и без списка: для каждого n отрезка проверить делители от 2 до √n — так дольше, но на сотне тысяч чисел тоже успевает.