Список простых чисел¶

Список простых чисел — перечень натуральных чисел, которые имеют ровно два различных натуральных делителя: единицу и само себя. Простые числа являются фундаментальными объектами теории чисел и используются в криптографии, математическом анализе и других областях. Поскольку множество простых чисел бесконечно, любой конечный список является фрагментом, ограниченным некоторым верхним пределом.

¶Определение и свойства

Простое число — это натуральное число больше единицы, которое не делится без остатка ни на одно другое натуральное число, кроме 1 и самого себя. Число 1 не считается простым, так как имеет только один делитель. Числа, имеющие более двух делителей, называются составными.

Основные свойства простых чисел:

• Наименьшее простое число — 2, это единственное чётное простое число.
• Все остальные простые числа являются нечётными.
• Основная теорема арифметики утверждает, что любое натуральное число, большее единицы, однозначно разлагается в произведение простых чисел (с точностью до порядка множителей).
• Множество простых чисел бесконечно — это было доказано Евклидом около 300 года до н. э. Его доказательство основано на предположении конечности списка и построении числа, не делящегося ни на одно из них.

¶Начало списка

Первые простые числа (до 100): 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Простые числа до 200: 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.

¶Методы построения списка

¶Решето Эратосфена

Наиболее известный алгоритм нахождения всех простых чисел до заданного предела — решето Эратосфена, предложенное древнегреческим математиком Эратосфеном Киренским в III веке до н. э. Алгоритм заключается в последовательном вычёркивании из списка натуральных чисел кратных каждому найденному простому числу. Для нахождения всех простых чисел до n достаточно вычеркнуть кратные простых чисел, не превышающих √n.

¶Тесты простоты

Для проверки отдельного числа на простоту используются детерминированные и вероятностные тесты. Детерминированный тест перебором делителей до √n применим лишь для небольших чисел. Для больших чисел применяются более эффективные методы:

• тест Миллера — Рабина (вероятностный);
• тест Соловея — Штрассена;
• тест AKS (детерминированный, полиномиальный, опубликован в 2002 году);
• тест Люка — Лемера для чисел Мерсенна.

¶Распределение простых чисел

Простые числа распределены неравномерно. С ростом чисел плотность простых чисел уменьшается. Согласно теореме о распределении простых чисел, количество простых чисел, не превышающих x, приблизительно равно x / ln x. Эта закономерность была доказана в 1896 году Адамаром и Валле-Пуссеном независимо друг от друга.

Гипотеза Римана, одна из нерешённых проблем математики, связана с точностью оценки распределения простых чисел и входит в список семи задач тысячелетия.

¶Специальные виды простых чисел

В математике выделяют классы простых чисел, обладающих дополнительными свойствами:

• Числа Мерсенна — простые числа вида 2p − 1, где p — простое. Крупнейшие известные простые числа относятся к этому типу. По состоянию на 2024 год наибольшее известное простое число — 2^82 589 933 − 1, найденное в 2018 году в рамках проекта GIMPS.
• Числа Ферма — числа вида 22n + 1. Известно лишь пять простых чисел Ферма: 3, 5, 17, 257, 65537.
• Простые-близнецы — пары простых чисел, отличающиеся на 2 (например, 11 и 13, 41 и 43). Гипотеза о бесконечности таких пар до сих пор не доказана.
• Палиндромические простые числа — простые числа, читающиеся одинаково слева направо и справа налево (например, 11, 101, 131).
• Простые Софи Жермен — простые числа p, для которых число 2p + 1 также простое.

¶Применение

Простые числа играют ключевую роль в современной криптографии. Алгоритмы RSA и Диффи — Хеллмана основаны на сложности разложения больших составных чисел на простые множители. Для генерации ключей используются простые числа длиной от 1024 до 4096 бит.

В других областях простые числа применяются:

• в хеш-функциях и генераторах псевдослучайных чисел;
• в теории кодирования для построения помехоустойчивых кодов;
• в акустике и музыкальной теории (обертоны простых частот);
• в биологии для изучения циклов появления цикад рода Magicicada, периоды которых выражаются простыми числами лет.

¶Исторические сведения

Изучение простых чисел началось в Древней Греции. Пифагорейцы знали о существовании простых чисел и их свойствах. Евклид в «Началах» доказал бесконечность множества простых чисел и сформулировал основную теорему арифметики. Эратосфен создал алгоритм их нахождения.

В XVII–XVIII веках Пьер Ферма, Леонард Эйлер и другие математики исследовали свойства простых чисел. Эйлер доказал, что сумма обратных величин всех простых чисел расходится. В XIX веке Пафнутий Чебышёв получил первые оценки распределения простых чисел, а Бернхард Риман сформулировал свою знаменитую гипотезу.

В XX веке с развитием вычислительной техники стало возможным находить и проверять простые числа огромных размеров. В 1951 году было найдено первое простое число, превышающее 10 000 000 знаков. В настоящее время поиск рекордных простых чисел ведётся распределёнными вычислениями.

¶Полные списки

Полные списки простых чисел публикуются в электронных базах данных, например в OEIS (Онлайн-энциклопедия целочисленных последовательностей). Для практических целей используются таблицы простых чисел до определённого предела, а также программные библиотеки, позволяющие генерировать их на лету. Наибольший практический интерес представляют списки до 10 000, 100 000 и 1 000 000, применяемые в учебных целях и при тестировании алгоритмов.