Простое число — это натуральное число больше 1, которое делится без остатка только на единицу и на само себя; таких чисел бесконечно много.
Когда вы вводите пароль в банковском приложении, защиту вашему соединению обеспечивают простые числа длиной в сотни цифр. Разобраться, что такое простое число, стоит не только школьнику перед контрольной — это основа теории чисел и современной криптографии. Ниже разберём определение, виды, способ находить простые числа вручную и причину их бесконечности.
Где применяется что такое простое число
Чаще всего про простые числа вспоминают в школе. Но реальных применений гораздо больше, и самое весомое из них — защита данных.
- Криптография. Алгоритм RSA, который шифрует банковские транзакции и HTTPS-соединения, строится на перемножении двух больших простых чисел. Восстановить их обратно из произведения вычислительно крайне тяжело — на этом и держится стойкость шифра.
- Хеш-таблицы. Программисты берут простое число как размер хеш-таблицы, чтобы ключи распределялись равномернее и возникало меньше коллизий.
- Генераторы псевдослучайных чисел. Многие алгоритмы используют большие простые числа в качестве модулей, чтобы последовательность не повторялась слишком рано.
- Проверка целостности данных. Контрольные суммы и некоторые коды коррекции ошибок опираются на свойства простых чисел.
Любопытно, что ещё сто лет назад теорию простых чисел считали чистой абстракцией без практической пользы. Криптография всё перевернула: теперь это индустрия на миллиарды долларов.
Читайте также
Как работает что такое простое число
В основе всё решает делимость. Число называют простым, если у него ровно два разных натуральных делителя: 1 и оно само. Если делителей больше — число составное.
Возьмём 7. Разделить его нацело можно только на 1 и на 7. Значит, 7 — простое. А вот 12 делится на 1, 2, 3, 4, 6 и 12 — шесть делителей, число составное.
Проверка «в лоб» выглядит так: берём число n и пробуем делить его на все числа от 2 до n−1. Если ни одно не делит нацело — число простое. На практике перебор можно сократить: достаточно проверять делители до квадратного корня из n. Если у числа есть делитель больше корня, то парный ему делитель обязательно меньше корня — и мы его уже нашли.
Первые простые числа запомнить несложно
| Простые числа до 30 | Почему именно они |
|---|---|
| 2, 3, 5, 7 | единственные делители — 1 и само число |
| 11, 13, 17, 19 | ни одно не делится на 2, 3 или 5 |
| 23, 29 | проверка делителей до корня не даёт делителя |
Число 2 стоит особняком — это единственное чётное простое число. Все прочие чётные числа делятся на 2, а значит, автоматически составные.
Простыми словами
Представьте, что у вас есть горсть монет и вы пытаетесь разложить их в ровные ряды — прямоугольником, без остатка.
Если монет 12, прямоугольник сложить легко: 3 на 4, 2 на 6. Число 12 «разбирается» на части. А если монет 7 — хоть как раскладывай, ровный прямоугольник не выходит. Только один длинный ряд 1 на 7. Вот это «неразбиваемое» число и есть простое.
Простые числа — как кирпичики, из которых собраны все остальные числа. Любое составное число можно разложить на простые множители, и обратно простое число уже не разложить. Поэтому их называют строительными блоками арифметики.
Как находить простые числа: решето Эратосфена
Чтобы найти все простые числа до какого-то предела, не обязательно проверять каждое по отдельности. Древнегреческий математик Эратосфен придумал быстрый способ ещё в III веке до н. э. — метод так и называют решето Эратосфена.
Алгоритм для чисел до 30
- Выпишите подряд все числа от 2 до 30.
- Первое невычеркнутое число — 2. Оно простое. Вычеркните все числа, кратные 2 (4, 6, 8, …).
- Следующее невычеркнутое — 3. Оно простое. Вычеркните кратные 3 (6, 9, 12, …).
- Следующее — 5. Вычеркните кратные 5.
- Продолжайте, пока не дойдёте до числа, квадрат которого больше предела.
- Все оставшиеся невычеркнутыми числа — простые.
Метод работает как сито: составные числа «просеиваются» и отсеиваются, а простые остаются. Для небольших диапазонов это удобнее любого перебора делителей вручную.
Антипример-ловушка: новички часто начинают вычёркивать с самого числа, а не с его квадрата. Для 5 нет смысла вычёркивать 10 и 15 заново — они уже вычеркнуты как кратные 2 и 3. Начинайте с 5×5=25, так быстрее.
Виды и типы простых чисел
Все простые числа равноправны по определению, но математики выделяют среди них особые группы с интересными свойствами.
- Простые числа-близнецы — пара простых чисел, отличающихся на 2: (3, 5), (11, 13), (17, 19). Существует ли таких пар бесконечно много — открытый вопрос, гипотеза о близнецах до сих пор не доказана.
- Числа Мерсенна — простые числа вида 2ⁿ − 1, например 3, 7, 31, 127. Именно среди них ищут самые большие известные простые числа: проверять их на простоту вычислительно удобнее.
- Чётное простое число — только одно, это 2. Все остальные простые числа нечётные.
- Ферма-простые — числа вида 2^(2ᵏ) + 1, например 3, 5, 17, 257.
Отдельно стоит сказать про число 1. Его исключили из простых чисел специально. Если бы единица считалась простой, разложение на множители перестало бы быть однозначным: 6 = 2 × 3, но и 6 = 1 × 2 × 3, и 6 = 1 × 1 × 2 × 3. Чтобы основная теорема арифметики работала чисто, 1 вынесли за скобки — она не простая и не составная.
Простое и составное число: в чём разница
Это две стороны одной медали. Каждое натуральное число больше 1 либо простое, либо составное — третьего не дано.
| Признак | Простое число | Составное число |
|---|---|---|
| Количество делителей | ровно 2 (1 и само) | три и более |
| Пример | 2, 3, 5, 7, 11 | 4, 6, 8, 9, 12 |
| Разложение на множители | не раскладывается | раскладывается на простые |
| Роль в арифметике | строительный блок | собрано из блоков |
Основная теорема арифметики утверждает: любое составное число раскладывается на простые множители единственным способом (с точностью до порядка). Например, 60 = 2 × 2 × 3 × 5. Другого набора простых множителей у 60 нет. Разложение на множители — главный инструмент, который превращает простые числа из абстракции в рабочий механизм: от сокращения дробей до взлома и защиты шифров.
Почему простых чисел бесконечно много
Этот факт доказал Евклид около 300 года до н. э., и его рассуждение — образец математической красоты. Доказательство идёт от противного.
Предположим, что простых чисел конечное число и мы выписали их все: p₁, p₂, …, pₙ. Перемножим их и прибавим единицу
N = (p₁ × p₂ × … × pₙ) + 1
Теперь посмотрим на N. При делении на любое из наших простых чисел оно даёт остаток 1 — значит, ни одно из них не делит N нацело. Но у любого числа есть хотя бы один простой делитель. Выходит, у N есть простой делитель, которого нет в нашем списке. Противоречие: список не был полным.
Значит, конечного списка простых чисел не существует. Их бесконечно много.
Математики пошли дальше и описали, как часто простые числа встречаются. Теорема о распределении простых чисел говорит: количество простых чисел, не превышающих x, примерно равно x / ln(x). Чем дальше по числовой прямой, тем реже попадаются простые — но они не кончаются никогда. Приблизительный размер n-го простого числа оценивают как n·ln(n).
Как использовать на практике
Если вам нужно работать с простыми числами, вот с чего начать.
Для ручной проверки небольшого числа на простоту делите его последовательно на 2, 3, 5, 7 и дальше по простым — до квадратного корня из числа. Дошли до корня без единого целого деления — число простое. Для 97: корень около 9,8, проверяем делители 2, 3, 5, 7. Ни один не подходит — 97 простое.
Для поиска всех простых чисел в диапазоне используйте решето Эратосфена — оно быстрее поштучной проверки. В программировании его реализуют массивом флагов: все элементы помечают как простые, затем вычёркивают кратные.
Если работаете с криптографией, помните главный принцип: стойкость шифра зависит от размера простых чисел. Для RSA берут простые числа длиной 1024 бита и больше. Генерируют их не перебором, а вероятностными тестами вроде теста Миллера — Рабина, которые быстро отсеивают составные числа.
Главное о простых числах
- Простое число — натуральное число больше 1, у которого ровно два делителя: единица и само число.
- Число 1 не относится ни к простым, ни к составным — иначе разложение на множители перестало бы быть однозначным.
- Число 2 — единственное чётное простое число, все остальные простые нечётные.
- Решето Эратосфена позволяет быстро найти все простые числа до заданного предела, отсеивая составные.
- Любое составное число единственным образом раскладывается на простые множители — это основная теорема арифметики.
- Простых чисел бесконечно много; это доказал Евклид методом от противного ещё около 300 года до н. э.
- На свойствах больших простых чисел держится криптография, включая алгоритм RSA.
Вопросы и ответы
Является ли число 1 простым?
Нет. Простое число по определению имеет ровно два делителя — единицу и само себя. У числа 1 только один делитель, поэтому его вынесли из классификации: оно не простое и не составное. Это сделано, чтобы основная теорема арифметики давала единственное разложение на множители.
Как быстро проверить, простое ли число?
Делите его на простые числа по порядку (2, 3, 5, 7, …) до квадратного корня из проверяемого числа. Если ни одно деление не выходит нацело — число простое. Для больших чисел в компьютерах применяют вероятностные тесты, например тест Миллера — Рабина.
Чем простое число отличается от составного?
У простого числа ровно два делителя, у составного — три и больше. Составное число всегда можно разложить на простые множители (12 = 2 × 2 × 3), а простое разложить уже нельзя. Каждое натуральное число больше 1 попадает строго в одну из этих категорий.
Какое самое большое известное простое число?
Рекорды регулярно обновляются и почти всегда это числа Мерсенна вида 2ⁿ − 1. Их ищут распределённые вычисления по всему миру. Актуальный рекорд стоит смотреть в официальных источниках — он меняется каждые несколько лет.
Источники:
- MATH 1332 Introduction to Mathematics — Prime Numbers (OER Texas Higher Ed)
- Lecture Notes — Number Theory I, MIT OpenCourseWare
- Lecture Notes: Number Theory and Cryptography — Washington University
- Prime Number Theorem Lecture Notes — University of Pennsylvania
