Что умеет этот калькулятор
Это инструмент «три в одном» для работы с простыми числами. Он умеет: (1) находить n-е простое число, \(\text{Prime}[n] = p_n\); (2) проверять, является ли заданное целое число простым, и показывать его порядковый номер в ряду простых чисел; (3) выводить список первых N простых чисел по запросу. Ряд простых начинается так: 2, 3, 5, 7, 11, 13, 17, … Простое число — это целое число больше 1, у которого нет других положительных делителей, кроме 1 и самого себя.
Как пользоваться
Выберите режим. В режиме 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\).
Разбор примера
Проверим число 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\).
Справочник простых чисел: первые 25 простых и контрольные точки индексов
Индекс \(n\) — это номер простого числа в возрастающей последовательности простых чисел, поэтому \(p_n\) обозначает \(n\)-е простое число. В таблице перечислены первые 25 простых чисел.
| n | pn | n | pn | n | pn | n | pn | n | pn |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 6 | 13 | 11 | 31 | 16 | 53 | 21 | 73 |
| 2 | 3 | 7 | 17 | 12 | 37 | 17 | 59 | 22 | 79 |
| 3 | 5 | 8 | 19 | 13 | 41 | 18 | 61 | 23 | 83 |
| 4 | 7 | 9 | 23 | 14 | 43 | 19 | 67 | 24 | 89 |
| 5 | 11 | 10 | 29 | 15 | 47 | 20 | 71 | 25 | 97 |
Контрольные точки индексов
| Утверждение | Значение | Смысл |
|---|---|---|
| \(p_{100}\) | 541 | 100-е простое число — 541 |
| \(p_{168}\) | 997 | 168-е простое число — 997, наибольшее простое число меньше 1000 |
| \(p_{1000}\) | 7919 | 1000-е простое число — 7919 |
| \(\pi(10)\) | 4 | Простые числа до 10: 2, 3, 5, 7 |
| \(\pi(100)\) | 25 | 25 простых чисел до 100 (последнее — 97) |
| \(\pi(1000)\) | 168 | 168 простых чисел до 1000 |
| \(\pi(10000)\) | 1229 | 1229 простых чисел до 10 000 |
Обратите внимание на связь между двумя обозначениями: если \(p\) простое, то \(\pi(p) = n\) тогда и только тогда, когда \(p = p_n\). Например, \(\pi(997) = 168\) и \(p_{168} = 997\).
Термины о простых числах
- Простое число: целое число больше 1, единственные положительные делители которого — 1 и само число (например, 2, 3, 5, 7, 11).
- Составное число: целое число больше 1, которое имеет хотя бы один делитель, отличный от 1 и от самого себя (например, 4, 6, 9, 15).
- 1 — особое число: число 1 не является ни простым, ни составным. У него только один положительный делитель — оно само.
- 2 — единственное чётное простое число: каждое другое чётное число делится на 2 и поэтому является составным.
- Индекс (порядковый номер) простого числа n: место простого числа в упорядоченном списке простых чисел. У 2 индекс 1, у 3 индекс 2, у 5 индекс 3 и так далее, поэтому \(p_n\) обозначает \(n\)-е простое число.
- Функция подсчёта простых чисел \(\pi(x)\): количество простых чисел, меньших или равных \(x\). Например, \(\pi(10) = 4\) и \(\pi(100) = 25\).
- Пробное деление: тест на простоту, при котором число \(p\) последовательно делят на каждое целое \(d\) от 2 до \(\sqrt{p}\). Если ни одно из них не делит \(p\) без остатка, то \(p\) простое. Проверять достаточно только до \(\sqrt{p}\), потому что в любой паре множителей один не превосходит \(\sqrt{p}\).
- Взаимно простые числа: два целых числа взаимно просты, если их наибольший общий делитель равен 1. Два разных простых числа всегда взаимно просты, но взаимно простые числа не обязательно являются простыми (например, 8 и 15 взаимно просты).
- Простые близнецы: пара простых чисел, которые отличаются на 2, например (3, 5), (11, 13), (17, 19), (29, 31) и (41, 43).