Постулат Бертрана и эффективные методы подсчёта простых чисел

Сегодня рассмотрим важную проблему теории чисел: как эффективно находить количество простых чисел в заданном интервале, например, от n+1 до 2n. Это связано с постулатом Бертрана (или теоремой Бертрана—Чебышёва), утверждающим, что для любого натурального числа n > 1 существует хотя бы одно простое число в интервале (n, 2n).

Звери проверяют числа на простые

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

Метод №1: Простая проверка делимости чисел интервала на их возможные делители (прямой подход)

Самый простой способ — проверить каждое число на простоту последовательной проверкой делимости. Для каждого числа k от n+1 до 2n проверим, делится ли оно на любое число от 2 до (k**0.5). Если ни на одно число не делится, добавляем к общему количеству.

Определение функции проверки на простоту (is_prime)

Эта функция определяет, является ли конкретное число простым:

Функция проверки числа на простоту (is_prime)

1. Фильтруем маленькие числа: Если число меньше 2, оно автоматически не простое. Поэтому сразу возвращаем False.
2. Проход по делителям: Дальше мы проверяем число на делимость. Обычно достаточно проверить числа от 2 до (k**0.5)​. То есть, если число делится на какое-то число меньше или равное своему квадратному корню, оно не простое. Вот почему верхний предел цикла ограничен (k**0.5).
3. Результат: Если цикл завершился успешно (не нашёл никаких делителей), значит, число простое, и возвращается True.

Основной цикл счёта простых чисел

Следующая часть программы занимается прохождением по каждому числу от n+1 до 2n и проверкой его на простоту:

Прохождение по каждому числу от n+1 до 2n и проверкой его на простоту

1. Создание счётчика: Переменная count инициализируется нулём. Она будет накапливать количество простых чисел.
2. Цикл прохода по числам: Для каждого числа x в интервале от n+1 до 2n проверяется, является ли оно простым, с помощью функции is_prime(x).
3. Накопление результата: Если число простое, увеличиваем счётчик на 1.
4. Возвращение результата: Возвращаем количество найденных простых чисел.

Интерфейс взаимодействия с пользователем

Программу запускают следующим образом:

Запуск программы. Ввод числа, вызов функции и вывод результата

Пример работы:
Пусть n=10. Нам нужно найти количество простых чисел в интервале (10,20). Простые числа здесь — это 11,13,17,19. Значит, программа должна вернуть 4.

Таблица с результатом проверки числа на простоту

Выводы:
Этот подход хорош своей простотой и наглядностью. Несмотря на очевидность, он достаточно медленный для больших значений n, так как для каждой отдельной проверки проводится полная серия делений. Для повышения производительности рекомендуется применять более продвинутые методы, такие как решето Эратосфена или смешанный подход.

Метод №2: Решето Эратосфена (Классический подход проверки числа на простое)

Один из наиболее эффективных методов для поиска простых чисел — это решето Эратосфена. Идея заключается в создании массива длины 2n, где каждая позиция соответствует числу, и поэтапном исключении всех составных чисел.

Решето Эратосфена - проверка числа на простое

Что происходит в коде. Находим количество простых чисел в интервале от n+1 до 2n. Принцип работы:

1. Функция проверки на простоту (is_prime)

Любое число меньше 2 не является простым. Для проверки, является ли число k простым, мы ищем делители от 2 до (k**0.5). Если найдём хотя бы один делитель, число не простое. Если нет — число простое.

2. Главный цикл

Проходим по каждому числу x от n+1 до 2n. Применяем функцию is_prime(x) для проверки каждого числа. Если число простое, увеличиваем счётчик.

3. Итоговый результат

В конце выводим количество найденных простых чисел.

Пример работы:

Допустим, n = 10. Надо найти простые числа в интервале (10, 20). Результаты:

• Число 11: простое (нет делителей).
• Число 12: не простое (делится на 2).
• Число 13: простое (нет делителей).
• Число 14: не простое (делится на 2)
• Число 19: простое (нет делителей).

Всего получается 4 простых числа: 11, 13, 17, 19.

Особенности:

• Простота реализации и понимания.
• Подходит для небольших значений n.
• Достаточно медленно работает для больших n, так как каждая проверка занимает заметное время.

Чуть поздней мы рассмотрим:

• Смешанный подход (комбинация решета и прямой проверки). Построим решето Эратосфена до некоторого фиксированного порога, а для остальных чисел проверим делимость вручную.
• Метод Аткина-Сейнвея (атакующий подход)