Как найти следующее простое число
Следующее простое число для целого n является первым простым p, которое строго больше n. Если исходное значение само простое, калькулятор не повторяет его. Для n = 2 ответ равен 3, для n = 17 ответ равен 19, а для n = 100 получается 101.
Определение удобно записать через минимум множества:
Символ ℙ обозначает множество простых чисел. Условие q > n отвечает за слово «следующее»: равенство запрещено. Поэтому задача отличается от проверки простоты и от поиска простого числа, ближайшего по абсолютному расстоянию. Ближайшее может находиться слева, а здесь движение всегда идёт только вверх.
Поиск начинается с n + 1. Для значений меньше 2 первым кандидатом становится 2. После этого чётные числа можно пропустить, потому что единственное чётное простое уже пройдено. Каждый нечётный кандидат проверяется пробным делением: достаточно искать делитель d, пока d ≤ candidate / d. Если делителя нет, найдено первое подходящее простое число, и поиск останавливается.
Что означают разница и число кандидатов
Главный результат p дополняют два показателя. Разница p − n показывает длину шага вправо по числовой прямой. Для 100 и 101 она равна 1, а для 1000 и 1009 равна 9. Это расстояние относится к конкретному исходному числу, а не к промежутку между двумя соседними простыми вообще.
Счётчик кандидатов показывает, сколько чисел алгоритм действительно проверил на простоту. После 2 чётные значения заранее пропускаются и в счётчик не входят. Например, после 14 проверяются 15 и 17, поэтому кандидатов два. Число 16 пропущено как заведомо составное.
Количество кандидатов не равно количеству операций деления. Для 1009 нужно проверить нечётные делители только до 31, а составной кандидат часто отбрасывается гораздо раньше. Число 1001 сразу делится на 7, поэтому до предела доходить не приходится.
Примеры поиска без двусмысленности
🔰 Старт с нуля. Для n = 0 ответ равен 2. Разница составляет 2, проверен один кандидат. Этот пример полезен для нумерации последовательности, когда до первого простого ещё нет положительной исходной точки.
🧱 Старт с единицы. Для n = 1 результат тоже равен 2, но разница уже равна 1. Единица не является простым числом, поэтому поиск не должен начинаться с 3.
➡️ Простое число на входе. Для n = 2 калькулятор возвращает 3, а не 2. Проверяется один кандидат. Такой контроль отличает строго следующее число от функции, которая ищет первое простое не меньше n.
🧩 Короткий составной участок. После 14 сначала проверяется 15. Оно делится на 3, поэтому поиск продолжается и заканчивается на 17. Результат 17, разница 3, проверено два нечётных кандидата.
⚡ Сосед справа. Для n = 100 первое же число 101 является простым. Разница и количество кандидатов равны 1. Такой случай показывает, что большой исходный аргумент не обязательно требует долгого поиска.
💻 Проверка генератора. После 1000 алгоритм рассматривает 1001, 1003, 1005, 1007 и 1009. Первые четыре значения составные, а 1009 простое. Получаем разницу 9 и пять проверенных кандидатов, что удобно для контрольного теста программы.
📚 Продолжение списка. После простого 29 следующим становится 31. Число 30 пропускается как чётное, затем проверяется 31. Если нужно сначала убедиться в свойствах самого 29, используйте проверку числа на простоту.
Границы и точность поиска
Исходное n должно быть целым числом от 0 до 1 000 000 000 000. Результат не ограничивается этой же верхней границей: если n стоит у её края, следующее простое число может оказаться немного больше. Калькулятор продолжает поиск, пока результат остаётся безопасным целым числом JavaScript.
Для n = 1 000 000 000 000 первое простое справа равно 1 000 000 000 039. Разница составляет 39. Поиск проверяет 20 нечётных кандидатов от 1 000 000 000 001 до результата включительно, а чётные значения между ними сразу отбрасывает.
Проверка каждого кандидата точная, без округления и случайных оснований. Сначала обрабатывается делимость на 2, затем перебираются нечётные делители. Для диапазона этой страницы такой прямой метод остаётся понятным и воспроизводимым. Для чисел с сотнями или тысячами цифр используют другие тесты и специализированные библиотеки.
Следующее простое не означает следующий член любой знакомой последовательности. Например, после числа Фибоначчи 13 следующее простое равно 17, но следующий член последовательности Фибоначчи равен 21. А примориал перемножает все простые числа до границы и отвечает на третью, отдельную задачу.
Вопросы о следующем простом числе
Фраза кажется однозначной, пока исходное число само не оказывается простым или рядом не появляется простое слева. Эти ответы фиксируют направление, строгую границу и способ подсчёта кандидатов.
Что будет, если исходное число уже простое?
Оно не возвращается повторно. Поиск начинается с n + 1 и выдаёт первое простое значение строго больше исходного. Поэтому после 17 следует 19.
Чем следующее простое отличается от ближайшего простого?
Следующее всегда находится справа и должно быть больше n. Ближайшее сравнивает расстояния в обе стороны. Для 12 ближайшим является 11, а следующим простым становится 13.
Почему после 0 и 1 результат равен 2?
Два является первым простым числом. Оно строго больше и 0, и 1, а меньших простых чисел не существует.
Учитываются ли чётные числа в количестве кандидатов?
После отдельного случая с числом 2 чётные значения не проверяются и в счётчик не входят. Для n = 14 считаются только 15 и 17, поэтому результат показывает два кандидата.
Может ли результат превысить верхнюю границу ввода?
Да. Ограничение 1 000 000 000 000 относится к исходному n. Следующее простое может быть немного больше, если оно остаётся безопасным целым числом для точного вычисления.
Всегда ли следующее простое существует?
Да. Простых чисел бесконечно много, поэтому для любого целого n существует простое число больше него. В пределах калькулятора поиск дополнительно ограничен безопасными целыми JavaScript.
Почему поиск пропускает чётные кандидаты?
Каждое чётное число больше 2 делится на 2 и является составным. После обработки первого простого числа проверка 4, 6, 8 и следующих чётных значений не добавляет информации.
Как проверить найденный результат вручную?
Убедитесь, что p больше n, затем проверьте, что каждое целое между ними составное. Для самого p достаточно исключить делители до √p включительно.
Похожие калькуляторы
Возможно вам пригодятся ещё несколько калькуляторов по данной теме:
- Проверка простого числа. Введите целое число от 0 до 1 000 000 000 000. Для составного числа калькулятор покажет несколько делителей.
- Калькулятор примориала. Введите целое n от 0 до 20 000. Калькулятор найдёт простые числа до n и перемножит их без округления.
- Калькулятор числа Фибоначчи. Введите индекс n от 0 до 40 000. Калькулятор вычислит Fₙ без округления и покажет соседние числа.
- Обычный калькулятор. Просто посчитайте чего вы там хотели.
- Рандомайзер: генератор случайных чисел. Выберите случайное число в нужном диапазоне для любых целей, в частности для розыгрышей и онлайн-лотерей в соцсетях.
- Бросить монетку онлайн. С помощью данной формы вы можете подбросить монетку онлайн любое количество раз.
- Калькулятор корней. Найдите правильное решение корней n-степени, включая квадратные и кубические.
- Калькулятор дробей. Выполните сложение, умножение, сокращение обыкновенных дробей.
- Калькулятор квадратных уравнений. Решите квадратные уравнения с помощью специальных формул, через дискриминант и по теореме Виета. Все способы решения сопровождаются примерами.
- Калькулятор сложного процента. Рассчитайте на инвесткалькуляторе сумму, полученную в результате применения сложного процента с реинвестированием, регулярным пополнением, капитализацией и с примерами.
Есть что добавить?
Напишите своё мнение, комментарий или предложение.