Конспект урока по информатике для подготовки к ЕГЭ
Тема: «Поиск простых чисел в заданном диапазоне с помощью алгоритма Решето Эратосфена» (с использованием Python).
Класс: 11
Тип урока: урок изучения нового материала и практического применения знаний
Цель: освоить алгоритм «Решето Эратосфена» для поиска простых чисел и научиться реализовывать его на языке программирования Python.
Задачи:
1. Организационный момент (2 мин)
2. Актуализация знаний (5 мин)
Вопросы для повторения:
3. Теоретическая часть (8 мин)
Определение: простое число – натуральное число, большее 1, которое делится только на 1 и само на себя.
История алгоритма: алгоритм «Решето Эратосфена» был разработан древнегреческим математиком Эратосфеном в III веке до н. э. Название связано с тем, что при ручном выполнении алгоритма «отсеиваются» составные числа, а остаются только простые — как бы «просеиваются через решето».
Принцип работы алгоритма:
Пример работы алгоритма для N=30:
Исходный список: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Сложность алгоритма: O(NloglogN) — практически линейная, что делает его эффективным для диапазонов до 107.
4. Практическая часть (15 мин)
Реализация на Python:
python
def sieve_of_eratosthenes(n):
# Создаём массив, где True означает, что число простое
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False # 0 и 1 не простые
p = 2
while p * p <= n:
if is_prime[p]:
# Отмечаем все кратные p как составные, начиная с p^2
for i in range(p * p, n + 1, p):
is_prime[i] = False
p += 1
# Собираем все простые числа в список
primes = [i for i in range(2, n + 1) if is_prime[i]]
return primes
# Пример использования
n = 30
print(f"Простые числа до {n}: {sieve_of_eratosthenes(n)}")
Разбор кода:
Оптимизация: для больших диапазонов можно пропускать чётные числа (кроме 2), сокращая память и время работы в 2 раза.
5. Решение задач (7 мин)
Задача 1 (базовый уровень): найдите все простые числа от 1 до 50 с помощью алгоритма. Проверьте результат вручную.
Задача 2 (повышенный уровень): напишите функцию, которая возвращает количество простых чисел в диапазоне [L,R]. Используйте «Решето Эратосфена».
Пример:
Задача 3 (ЕГЭ -стиль): определите, сколько простых чисел находится в диапазоне от 100 до 200. Реализуйте решение на Python и выведите результат.
6. Подведение итогов (5 мин)
7. Домашнее задание (3 мин)
Методические рекомендации:
Ресурсы для самостоятельного изучения: