Калькулятор следующего простого числа

Как калькулятор находит следующее простое число

Введите неотрицательное целое n. Калькулятор найдёт первое простое число p, которое строго больше n, а затем покажет расстояние до него и число проверенных нечётных кандидатов.

Почему исходное число не входит в ответ

Слово «следующее» задаёт строгое условие p > n. Если ввести простое число 17, результатом будет 19. Само число 17 не подходит, хотя оно и простое.

Поиск начинается с n + 1. Для значений меньше 2 ответом становится 2. Дальше чётные числа можно пропускать: любое чётное целое больше 2 делится на 2 и является составным.

Как проверяется кандидат

Для нечётного кандидата перебираются нечётные делители, пока d ≤ candidate / d. Это та же граница, что √candidate, но без промежуточного округления. Если точного деления нет, число простое и поиск заканчивается.

Контрольные примеры

После 0 идёт 2. Разница равна 2, проверен один кандидат. Ноль не относится ни к простым, ни к составным числам.

После 2 идёт 3. Исходное простое число не повторяется. Разница равна 1, кандидат тоже один.

После 14 идёт 17. Сначала проверяется 15, которое делится на 3. Затем проверяется простое 17. Разница равна 3, кандидатов два.

После 1000 идёт 1009. Алгоритм проверяет 1001, 1003, 1005, 1007 и 1009. Первые четыре числа составные. Получается разница 9 и пять кандидатов.

1. Сравните ответ с n: он должен быть больше.
2. Убедитесь, что числа между n и p составные.
3. Проверьте, что у p нет делителей до квадратного корня включительно.

Как читать дополнительные показатели

Разница p - n показывает обычное расстояние по числовой прямой. Счётчик кандидатов устроен иначе: он учитывает только нечётные числа, которые действительно проверялись на простоту. Пропущенные чётные числа в него не входят.

Количество кандидатов не равно количеству делений. Число 15 отбрасывается сразу по делителю 3, а для простого 101 нужно исключить все подходящие делители до 10.

Ограничение ввода. Можно вводить целые числа от 0 до 1 000 000 000 000. Для верхней границы ответ равен 1 000 000 000 039, разница составляет 39, а число нечётных кандидатов равно 20. Результат точный и не округляется.

Похожие калькуляторы

Вам могут пригодиться следующие калькуляторы на эту же тему:

• Калькулятор Z-оценки. Сравните значение со средним своей группы или восстановите исходное число по известной Z-оценке.
• Калькулятор НОК. Введите два целых числа длиной до 100 цифр каждое, чтобы точно найти их НОК.
• Калькулятор НОД. Введите два целых числа длиной до 100 цифр каждое, чтобы точно найти их НОД.
• Калькулятор цифрового корня. Введите целое число длиной до 10 000 цифр, чтобы свести его к одной цифре и увидеть ход расчёта.
• Калькулятор сочетаний. Введите общее число элементов и размер выборки, чтобы получить точное количество возможных групп.
• Калькулятор деления с остатком. Введите целое делимое и ненулевой делитель, чтобы найти частное и единственный евклидов остаток.
• Конвертер градусов в радианы. Введите угол в градусах или радианах, и второе поле сразу покажет эквивалентное значение.
• Проверка простого числа. Введите целое число, чтобы определить, простое оно, составное или относится к особым случаям.
• Калькулятор суперфакториала. Введите целое n, чтобы перемножить все факториалы от 1! до n!.
• Калькулятор примориала. Введите целую границу n, чтобы перемножить все простые числа, которые её не превосходят.

Поделиться в социальных сетях

Если вам понравилось, пожалуйста, поделитесь этим калькулятором в социальных сетях. Это просто для вас и полезно для продвижения проекта. Спасибо!