🔢 Простое число — это натуральное число, большее 1, которое имеет ровно два натуральных делителя: единицу и само себя. Иными словами, оно делится без остатка только на 1 и на себя. Например, 2, 3, 5, 7, 11 — простые числа. Числа, имеющие более двух делителей, называются составными. Единица не считается простым числом, так как у неё только один делитель.
📊 Таблица первых простых чисел
| № | Простое число |
|---|---|
| 1 | 2 |
| 2 | 3 |
| 3 | 5 |
| 4 | 7 |
| 5 | 11 |
| 6 | 13 |
| 7 | 17 |
| 8 | 19 |
| 9 | 23 |
| 10 | 29 |
| 11 | 31 |
| 12 | 37 |
| 13 | 41 |
| 14 | 43 |
| 15 | 47 |
🔍 Основные свойства
- 🔹 Множество простых чисел бесконечно (доказано Евклидом).
- 🔹 2 — единственное чётное простое число; все остальные чётные числа делятся на 2 и потому составные.
- 🔹 Каждое простое число, кроме 2 и 3, представимо в виде 6k ± 1 (где k — натуральное число).
- 🔹 Любое натуральное число больше 1 либо является простым, либо раскладывается в произведение простых множителей единственным способом (с точностью до порядка) — это основная теорема арифметики.
- 🔹 Если число n не делится ни на одно простое число ≤ √n, то оно простое (метод пробных делений).
⚙️ Применение простых чисел
- 🔐 Криптография: алгоритмы шифрования (RSA, Диффи — Хеллман) основаны на трудности разложения большого числа на простые сомножители.
- 🔗 Генерация случайных чисел: простые числа используются в хешировании и контрольных суммах.
- 🧮 Теория кодирования: корректирующие коды, циклические коды опираются на свойства простых чисел.
🕰️ Историческая справка
Простые числа изучали ещё в Древней Греции. Евклид в III веке до н.э. в «Началах» доказал бесконечность их множества. Эратосфен Киренский предложил алгоритм «решето Эратосфена» для отсеивания простых чисел. В XVII веке Пьер Ферма внёс вклад в теорию, выдвинув гипотезу о числах вида 22n+1 (числа Ферма). Леонард Эйлер позже опроверг её для n=5. Марин Мерсенн исследовал числа вида 2p−1 (числа Мерсенна), многие из которых оказались простыми. Сегодня поиск больших простых чисел важен для криптографии и тестирования вычислительных систем.
📚 Энциклопедический блок
Распределение простых чисел. Функция π(x) — количество простых, не превышающих x. Теорема о распределении простых чисел утверждает, что π(x) ~ x / ln x. Несмотря на видимую хаотичность, простые числа подчиняются асимптотическому закону. Глубинные вопросы об их распределении связаны с гипотезой Римана (1859), которая до сих пор не доказана и входит в список «задач тысячелетия».
Простые числа-близнецы: пары (p, p+2), например (3,5), (11,13). Гипотеза о бесконечности близнецов остаётся открытой. Самое большое известное простое число (по состоянию на 2024 год) — число Мерсенна M82589933, найденное в рамках проекта GIMPS, содержит более 24 миллионов десятичных знаков.
❓ FAQ по смежным темам
- Что такое составное число?
- Составное число — натуральное число, большее 1, которое имеет более двух делителей, т.е. раскладывается в произведение меньших натуральных чисел. Например, 4 (делители 1,2,4), 6, 8, 9 и т.д.
- Почему 1 не является простым числом?
- По определению, простое число должно иметь ровно два различных делителя. У единицы только один делитель — она сама. Кроме того, исключение 1 из простых чисел сохраняет однозначность разложения на простые множители (основную теорему арифметики).
- Как быстро проверить, является ли число простым?
- Для небольших чисел (до нескольких миллионов) работают пробные деления до √n. Для больших чисел применяют вероятностные тесты (Миллера — Рабина) и детерминированные (AKS, тест Люка — Лемера для чисел Мерсенна).
- Что такое решето Эратосфена?
- Алгоритм нахождения всех простых чисел до заданного предела N. Выписываются последовательные числа от 2 до N, затем начиная с 2 вычёркиваются все кратные ему, далее берётся следующее невычеркнутое число и повторяется процесс. Оставшиеся числа — простые.
- Какое максимальное известное простое число?
- На 2024 год рекордсмен — M82589933 = 282589933 − 1, открытое в 2018 году. Оно содержит 24 862 048 десятичных цифр.
