Простые числа

Числа, которые делятся только сами на себя, например 7, 11, 13 – простые числа. Люди давно заметили, что числа бывают двух разных сортов. Например, число 12 можно без остатка разделить на 2, 3, 4 и 6. А следующее за ним число 13 делится без остатка только само на себя: 13/13 = 1. Кроме того, каждое число делится на один. Такие числа, как 12 или 15, которые можно разделить на какое-нибудь другое, меньшее, называются составными. Самое маленькое простое число – 2. Первые простые числа составил в виде таблицы Эратосфен (так называемое "решето Эратосфена") и заметил, что многие простые числа группируются в пары близнецов: таковы 11 и 13, 29 и 31, 41 и 43. Самым маленьким непростым, или составным, числом (кроме 1) является 4.

Числа, которые делятся только сами на себя, например 7, 11, 13 – простые числа

Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа - элементарные "строительные блоки" натуральных. Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа.

Простые числа можно найти с помощью "решета Эратосфена", "решета Сундарама" и "решета Аткина". На практике же вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Существует множество полиномиальных тестов простоты, но большинство их являются вероятностными и используются для нужд криптографии.

Наибольшим известным простым числом по состоянию на август 2014 года является 257885161 - 1.

Инструменты