Прості числа

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

Основна теорема арифметики стверджує, що кожне натуральне число, більше одиниці, можна представити у вигляді добутку простих чисел, причому єдиним способом з точністю до порядку слідування співмножників. Таким чином, прості числа – елементарні "будівельні блоки" натуральних. Подання натурального числа у вигляді добутку простих називається розкладанням на прості або факторизацією числа.

Прості числа можна знайти за допомогою "решета Ератосфена", "решета Сундарама" та "решета Аткіна". На практиці замість отримання списку простих чисел часто потрібно перевірити, чи є дане число простим. Алгоритми, які вирішують це завдання, називаються тестами простоти. Існує безліч поліноміальних тестів простоти, але більшість їх є імовірнісними та використовуються для потреб криптографії.

Найбільшим відомим простим числом станом на серпень 2014 року було 2^57885161 - 1.