Как найти простые числа в диапазоне в Python

В этой статье мы разберём решения задачи по нахождению простых чисел из указанного диапазона в Python. Рассмотрим 3 метода. Начнём с самых простого и перейдём к более эффективным.

Метод прямого перебора для нахождения простых чисел в Python

Метод прямого перебора является самым базовым способом нахождения простых чисел в заданном диапазоне. Простое число — это натуральное число, большее единицы, которое делится без остатка только на 1 и на само себя. А значит мы можем просто перебрать все числа, проверяя на соответствие данным условиям.

Сначала посмотрим код, а потом разберём как он работает:

# Запрос нижней и верхней границы диапазона у пользователя
lower = int(input("Введите нижнюю границу диапазона: "))
upper = int(input("Введите верхнюю границу диапазона: "))

# Список для хранения найденных простых чисел
primes = []

# Перебор каждого числа в заданном диапазоне
for num in range(lower, upper + 1):
    # Все числа меньше 2 не могут быть простыми
    if num > 1:
        for i in range(2, num):
            if (num % i) == 0:
                break
        else:
            primes.append(num)

# Вывод найденных простых чисел
print(f"Простые числа между {lower} и {upper}: {primes}")

Объяснение кода

1. Ввод диапазона: Программа запрашивает у пользователя ввести нижнюю (lower) и верхнюю (upper) границы диапазона для поиска простых чисел. Эти значения преобразуются в целые числа с помощью функции int().
2. Инициализация списка primes: Создается пустой список primes, в который будут добавляться найденные простые числа.
3. Перебор чисел в диапазоне: С помощью внешнего цикла for программа перебирает каждое число в заданном диапазоне от lower до upper включительно.
4. Проверка условий: Для каждого числа num в диапазоне выполняется проверка на делимость всеми числами от 2 до num - 1. Если находится делитель, внутренний цикл прерывается командой break.
5. Добавление простого числа: Если для числа num не найдено ни одного делителя (кроме 1 и самого числа), оно считается простым и добавляется в список primes.
6. Вывод результата: После завершения всех проверок программа выводит список primes, содержащий все простые числа в заданном диапазоне.

Оптимизированный метод перебора для нахождения простых чисел в Python

Оптимизированный метод перебора для нахождения простых чисел в диапазоне улучшает базовый алгоритм прямого перебора, уменьшая количество необходимых операций. Этот метод включает в себя несколько математических ухищрений, которые позволяют сократить количество проверок делимости для каждого числа.

Принципы оптимизации

1. Проверка делителей только до корня из числа: Для определения, является ли число простым, достаточно проверить его делимость всеми числами до квадратного корня из этого числа. Если до этого момента делитель не найден, число можно считать простым.
2. Игнорирование четных чисел: Кроме 2, все простые числа — нечетные. Это означает, что после проверки числа 2 можно игнорировать все четные числа, удваивая шаг при переборе потенциальных делителей.

Сначала посмотрим код, а потом разберём как он работает:

import math

lower = int(input("Введите нижнюю границу диапазона: "))
upper = int(input("Введите верхнюю границу диапазона: "))

primes = []
for num in range(lower, upper + 1):
    # Пропускаем 1 и все четные числа, кроме 2
    if num < 2 or (num % 2 == 0 and num > 2):
        continue
    # Проверяем делителей только до корня из числа
    limit = int(math.sqrt(num)) + 1
    for i in range(2, limit):
        if num % i == 0:
            break
    else:
        primes.append(num)

print(f"Простые числа между {lower} и {upper}: {primes}")

Объяснение кода

• Импорт модуля math: Для вычисления квадратного корня из числа используется функция math.sqrt().
• Ввод границ диапазона: Пользователь вводит нижнюю и верхнюю границы диапазона для поиска простых чисел.
• Перебор чисел в диапазоне: Цикл for перебирает каждое число в заданном диапазоне, пропуская 1 и все четные числа, кроме 2.
• Проверка на делимость: Для каждого числа выполняется проверка на делимость числами до его квадратного корня. Если делитель найден, цикл прерывается.
• Добавление простого числа: Если число проходит все проверки, оно добавляется в список простых чисел.

Преимущества метода

Оптимизированный метод перебора значительно увеличивает эффективность поиска простых чисел, особенно для больших диапазонов, благодаря сокращению количества необходимых проверок. Этот подход делает алгоритм более быстрым и позволяет находить простые числа затрачивая меньше ресурсов и времени.

Реализация «Решето Эратосфена» в Python для нахождения простых чисел

Решето Эратосфена — это эффективный алгоритм, который позволяет найти все простые числа в заданном диапазоне до любого заданного предела. Этот алгоритм был разработан древнегреческим математиком Эратосфеном. Алгоритм основан на идее последовательного исключения кратных чисел, начиная с первых простых чисел.

Принцип работы алгоритма

1. Инициализация списка: Создается список (или массив) чисел от 2 до заданного верхнего предела. Все числа сначала считаются потенциально простыми.
2. Итеративное исключение кратных: Для каждого числа в списке, начиная с 2, исключаются все его кратные в диапазоне, начиная с квадрата этого числа. Это делается потому, что кратные меньших чисел уже будут исключены на предыдущих шагах.
3. Выборка простых чисел: По завершении процесса в списке останутся только простые числа.

Сначала посмотрим код, а потом разберём как он работает:

def sieve_of_eratosthenes(limit):
    prime_flags = [True] * (limit + 1)  # Инициализируем список флагов простых чисел
    p = 2
    while (p ** 2 <= limit):
        # Если prime_flags[p] не изменен, значит p простое
        if (prime_flags[p] == True):
            # Исключаем все кратные p
            for i in range(p ** 2, limit + 1, p):
                prime_flags[i] = False
        p += 1
    # Собираем все простые числа
    primes = [p for p in range(2, limit + 1) if prime_flags[p]]
    return primes

# Пример использования функции
limit = 100
print(f"Простые числа до {limit}: {sieve_of_eratosthenes(limit)}")

Объяснение кода

• Инициализация: Создается список prime_flags, где каждый индекс представляет число, а значение по умолчанию True указывает на то, что число пока считается простым.
• Итерация: Цикл продолжается до тех пор, пока квадрат текущего числа p меньше или равен пределу. Это гарантирует, что все кратные числа будут правильно исключены.
• Исключение кратных: Для каждого числа p, если оно все еще считается простым (prime_flags[p] == True), исключаются все его кратные начиная с p^2 до верхнего предела с шагом p.
• Выборка простых чисел: В конце, из списка флагов собираются индексы чисел, которые все еще считаются простыми.

Преимущества метода

Решето Эратосфена предлагает значительное улучшение производительности по сравнению с методами прямого перебора за счет сокращения количества необходимых проверок делимости. Этот метод идеально подходит для быстрого нахождения всех простых чисел в больших диапазонах.

Недостатки метода

Основной недостаток алгоритма заключается в том, что он требует большего объема памяти для хранения списка флагов, особенно при работе с очень большими диапазонами.