Калькулятор простых чисел (поиск n-го простого и проверка на простоту)

Введите расчет

Режим n-е простое число (найти Prime[n]) Проверка на простоту (является ли число простым?) Список первых N простых чисел

Номер простого числа n (нумерация с 1)

Число для проверки

Сколько простых чисел вывести (N)

Результатов

Prime[100] — the 100th prime number

541

Номер простого числа n	100
n-е простое число, Prime[n]	541

Что умеет этот калькулятор

Это инструмент «три в одном» для работы с простыми числами. Он умеет: (1) находить n-е простое число, \(\text{Prime}[n] = p_n\); (2) проверять, является ли заданное целое число простым, и показывать его порядковый номер в ряду простых чисел; (3) выводить список первых N простых чисел по запросу. Ряд простых начинается так: 2, 3, 5, 7, 11, 13, 17, … Простое число — это целое число больше 1, у которого нет других положительных делителей, кроме 1 и самого себя.

Простые числа (2, 3, 5, 7, 11, 13, 17, 19) отмечены на числовой прямой; составные оставлены без выделения.

Как пользоваться

Выберите режим. В режиме n-е простое число укажите номер позиции \(n\) (нумерация с единицы, например 100) — калькулятор вернёт \(\text{Prime}[100] = 541\). В режиме проверка на простоту введите любое целое число (например 97), и сервис сообщит, является ли оно простым, а если да — какой у него номер \(n\) в ряду простых чисел. В режиме список первых N простых укажите нужное количество простых чисел, и вы получите полный список через запятую, а также самое большое из них — \(\text{Prime}[N]\).

Как это работает

Проверка на простоту выполняется методом пробного деления: число \(p\) является простым, если у него нет ни одного целого делителя в диапазоне от 2 до квадратного корня из \(p\). Достаточно проверять только нечётные делители \(d\) (после отдельной обработки двойки), пока выполняется условие \(d \cdot d \le p\) — это быстро и избавляет от ошибок округления с плавающей точкой. n-е простое число находится перебором кандидатов 2, 3, 4, … с подсчётом каждого простого числа, пока счётчик не достигнет \(n\). Порядковый номер простого числа \(m\) равен \(\pi(m)\) — количеству простых чисел, не превосходящих \(m\).

Реклама

Каждый индекс \(n\) соответствует своему простому \(p_n\): 1→2, 2→3, 3→5, 4→7.

Разбор примера

Проверим число 97. Оно нечётное, поэтому пробуем делители \(d = 3, 5, 7, 9\) (поскольку \(9^2 = 81 \le 97\), а \(11^2 = 121 > 97\)). Ни один из них не делит 97 нацело, значит, 97 — простое число. Если подсчитать все простые числа до 97 включительно — 2, 3, 5, …, 97, — их окажется 25. Следовательно, 97 — это 25-е простое число: \(\text{primeIndex} = 25\).

Частые вопросы

Является ли 1 простым числом? Нет. По определению простое число должно быть больше 1, поэтому единица не считается ни простым, ни составным числом.

Какое единственное чётное простое число? Это 2 — единственное чётное простое число; все остальные чётные числа делятся на 2.

Какое число стоит на 100-м месте? \(\text{Prime}[100] = 541\). Несколько других контрольных точек: \(\text{Prime}[10] = 29\), \(\text{Prime}[25] = 97\), \(\text{Prime}[50] = 229\), \(\text{Prime}[223] = 1409\).