Введите с клавиатуры число N и вычислите все простые числа в диапазоне от 2 до N, используя решето Эратосфена

Решето Эратосфена — это эффективный алгоритм для нахождения всех простых чисел до заданного предела. Давайте разберём этот алгоритм шаг за шагом. ### Шаг 1: Что такое простые числа? Простые числа — это числа больше 1, которые не имеют делителей, кроме 1 и самого себя. Например, 2, 3, 5, 7, 11 — это простые числа. ### Шаг 2: Как работает решето Эратосфена? Алгоритм решета Эратосфена выполняется следующим образом: 1. **Создание списка:** Создайте список (или массив) чисел от 2 до N (где N — верхний предел, заданный пользователем). 2. **Инициализация:** Все числа изначально помечаются как простые. 3. **Выбор первого простого числа:** Начните с первого числа в списке (число 2). 4. **Выбор кратных:** Удалите из списка все кратные текущему простому числу (например, для 2 удаляем 4, 6, 8 и т.д.). Эти числа не могут быть простыми. 5. **Повторение:** Перейдите к следующему числу в списке, которое отмечено как простое, и повторите шаг 4. 6. **Завершение:** Продолжайте процесс, пока текущее простое число не превышает √N. Все оставшиеся числа в списке — это простые числа. ### Шаг 3: Пример реализации Теперь давайте посмотрим, как это можно реализовать на Python. Вот пример кода, который выполняет вышеперечисленные шаги: ```python def sieve_of_eratosthenes(n): if n < 2: return [] # Инициализируем список простых чисел is_prime = [True] * (n + 1) # Список от 0 до N включительно is_prime[0] = is_prime[1] = False # 0 и 1 не являются простыми for p in range(2, int(n**0.5) + 1): # Проверяем числа до √N if is_prime[p]: # Если p простое for multiple in range(p * p, n + 1, p): # Удаляем кратные p is_prime[multiple] = False # Собираем все простые числа в список primes = [p for p in range(2, n + 1) if is_prime[p]] return primes # Ввод пользователя N = int(input("Введите число N: ")) primes = sieve_of_eratosthenes(N) print(f"Простые числа от 2 до {N}: {primes}") ``` ### Шаг 4: Объяснение кода 1. **Инициализация:** Мы создаём список `is_prime`, где каждый элемент изначально помечен как `True`. Значения для 0 и 1 устанавливаются в `False`, так как они не простые. 2. **Внешний цикл:** Мы проходим по всем числам от 2 до квадратного корня из N. 3. **Внутренний цикл:** Если текущий элемент является простым, мы начинаем удалять все его кратные числа, устанавливая соответствующие значения в `False`. 4. **Сбор простых чисел:** В конце мы собираем все индексы, у которых стоит `True`, и возвращаем их как список простых чисел. ### Заключение Таким образом, с помощью алгоритма решета Эратосфена мы можем эффективно находить все простые числа до заданного значения N. Этот подход позволяет значительно сократить количество необходимых вычислений по сравнению с проверкой каждого числа на простоту индивидуально.