Введите с клавиатуры число 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. Вот пример кода, который выполняет вышеперечисленные шаги:

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. Этот подход позволяет значительно сократить количество необходимых вычислений по сравнению с проверкой каждого числа на простоту индивидуально.