Урок: Алгоритм «Решето Эратосфена» для поиска простых чисел Цели урока Познакомить учащихся с методом поиска простых чисел Научить применять алгоритм «Решето Эратосфена» Развить алгоритмическое мышление Необходимые знания Понятие простых и составных чисел Признаки делимости чисел Базовые навыки работы с числами Теоретическая часть Простые числа - это натуральные числа, которые делятся только на 1 и на себя. Решето Эратосфена - это древний алгоритм для нахождения всех простых чисел до заданного числа n. Алгоритм работает следующим образом: 1. 2. 3. 4. 5. Записываем все числа от 1 до n Число 1 не является ни простым, ни составным - исключаем его Первое простое число - 2. Вычеркиваем все числа, кратные 2 (кроме самого 2) Следующее простое число - 3. Вычеркиваем все числа, кратные 3 (кроме самого 3) Повторяем процесс для следующих простых чисел до тех пор, пока возможно Практическая часть Рассмотрим пример поиска простых чисел от 1 до 100: 1. 2. 3. 4. 5. Записываем числа: 1, 2, 3, 4, 5, …, 100 Вычеркиваем 1 Вычеркиваем числа, кратные 2 (4, 6, 8, 10, …) Вычеркиваем числа, кратные 3 (9, 12, 15, 18, …) Продолжаем с числами 5, 7 и т.д. Решение задачи Найдем простые числа от 1 до 50: 1. Записываем числа: 1, 2, 3, 4, 5, …, 50 2. Вычеркиваем 1 3. Вычеркиваем числа, кратные 2 (4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50) 4. Вычеркиваем числа, кратные 3 (9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48) 5. Вычеркиваем числа, кратные 5 (25, 30, 35, 40, 45, 50) 6. Вычеркиваем числа, кратные 7 (49) Ответ: Простые числа от 1 до 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 Домашнее задание 1. Найти все простые числа от 1 до 70 2. Объяснить, почему число 1 не является простым 3. Придумать свой способ проверки числа на простоту Дополнительные материалы Таблица простых чисел Карточки с числами для практической работы Интерактивная доска для демонстрации алгоритма Критерии оценивания Правильность выполнения алгоритма Умение объяснять каждый шаг Скорость выполнения задания Точность полученных результатов
