Простые числа: определение, таблица до 100 и методы проверки
Простое число — это натуральное число больше 1, делящееся только на 1 и на себя. Их список бесконечен. Проверить число на простоту можно делением до квадратного корня или алгоритмами вроде решета Эратосфена.
Оглавление
Что такое простое число
В арифметике простыми называют натуральные числа $n > 1$, которые не имеют других делителей, кроме единицы и самого себя. Это фундамент теории чисел, на котором строятся разложения на множители, модульная арифметика и современная криптография.
Основные свойства:
- У любого простого числа ровно два натуральных делителя.
- Число 1 не является простым, так как имеет единственный делитель.
- Число 2 — единственное чётное простое число. Все остальные чётные значения автоматически составные, поскольку делятся на 2.
- Любое натуральное число больше 1 либо простое, либо раскладывается в произведение простых множителей (основная теорема арифметики).
Не путайте простые числа с составными. Составные числа (4, 6, 8, 9, 10...) всегда имеют три и более делителя.
Список первых простых чисел
Множество простых чисел бесконечно, что было строго доказано Евклидом. Для учебных задач, олимпиад и быстрой проверки достаточно знать значения в диапазоне от 1 до 100.
Первые 25 простых чисел (до 100)
| № | Число | Делители |
|---|---|---|
| 1 | 2 | 1, 2 |
| 2 | 3 | 1, 3 |
| 3 | 5 | 1, 5 |
| 4 | 7 | 1, 7 |
| 5 | 11 | 1, 11 |
| 6 | 13 | 1, 13 |
| 7 | 17 | 1, 17 |
| 8 | 19 | 1, 19 |
| 9 | 23 | 1, 23 |
| 10 | 29 | 1, 29 |
| 11 | 31 | 1, 31 |
| 12 | 37 | 1, 37 |
| 13 | 41 | 1, 41 |
| 14 | 43 | 1, 43 |
| 15 | 47 | 1, 47 |
| 16 | 53 | 1, 53 |
| 17 | 59 | 1, 59 |
| 18 | 61 | 1, 61 |
| 19 | 67 | 1, 67 |
| 20 | 71 | 1, 71 |
| 21 | 73 | 1, 73 |
| 22 | 79 | 1, 79 |
| 23 | 83 | 1, 83 |
| 24 | 89 | 1, 89 |
| 25 | 97 | 1, 97 |
Запомните «близнецов» — пары простых чисел, разность которых равна 2: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73). Это ускоряет работу с числовыми рядами.
Как проверить число на простоту
Выбор метода зависит от величины числа и доступных ресурсов. Ниже приведены практичные способы, от ручных до программных.
1. Проверка последовательным делением Подходит для чисел до $10^5$. Не нужно проверять все делители от 2 до $n-1$. Достаточно проверить делимость только на простые числа, квадрат которых не превышает $n$. Шаги:
- Если число чётное и $>2$ — оно составное.
- Последовательно делите на 3, 5, 7, 11, 13…
- Остановитесь, когда проверяемый делитель превысит $\sqrt{n}$. Если остаток не равен нулю ни разу, число простое.
Пример: Проверим 97. $\sqrt{97} \approx 9.8$. Проверяем 2, 3, 5, 7. Ни на одно не делится. Вывод: 97 простое.
2. Быстрые признаки делимости Позволяют мгновенно отсеять составные числа:
- На 2: последняя цифра 0, 2, 4, 6, 8.
- На 3: сумма цифр делится на 3 (например, $123 \rightarrow 1+2+3=6$ — составное).
- На 5: последняя цифра 0 или 5.
- На 11: разность сумм цифр на чётных и нечётных позициях кратна 11.
3. Решето Эратосфена Классический алгоритм для поиска всех простых чисел в заданном диапазоне. Выписывается ряд чисел, последовательно вычёркиваются кратные 2, 3, 5 и т.д. Оставшиеся значения — простые. Идеален для школьных задач и базовых алгоритмов.
Для чисел от $10^6$ и выше ручной перебор неэффективен. В программировании и криптографии используют вероятностные тесты (Миллера–Рабина) или детерминированный АКР-тест, дающие результат за доли секунды.
Частые ошибки
- Считать единицу простым числом. По определению у простого числа ровно два делителя, у 1 — только один. Это исключение зафиксировано в математике с XIX века.
- Игнорировать число 2. Многие механически исключают все чётные числа, забывая, что 2 — базовый элемент последовательности.
- Проверять делители до самого числа. Это удваивает вычисления без пользы. Достаточно идти до $\sqrt{n}$.
- Путать простые и взаимно простые числа. Например, 8 и 9 составные, но взаимно простые (их НОД = 1). Это разные математические свойства.
FAQ
Сколько всего существует простых чисел? Бесконечно много. Доказательство основано на методе от противного: если предположить, что список конечен, можно построить новое число, которое не делится ни на одно из известных простых, что создаёт противоречие.
Какое самое большое известное простое число? На 2026 год крупнейшие найденные числа относятся к классу простых чисел Мерсенна ($M_p = 2^p - 1$, где $p$ тоже простое). Они содержат десятки миллионов цифр и обнаруживаются в рамках распределённых вычислений GIMPS.
Зачем нужны простые числа в повседневной жизни? Они лежат в основе асимметричной криптографии (RSA, ECC). Безопасность онлайн-платежей, HTTPS-соединений, цифровых подписей и защищённых мессенджеров напрямую зависит от сложности разложения больших чисел на простые множители.
Могут ли простые числа быть отрицательными или дробными? Нет. В классической теории чисел рассматриваются только натуральные числа ($\mathbb{N} = {2, 3, 4, ...}$). Дроби, иррациональные и отрицательные значения в этот список не входят.