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


Просто́е число́ — натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число является простым, если оно отлично от и делится без остатка только на и на само [1].

Пример: число простое (делится на и на ), а не является простым, так как, помимо и , делится на  — имеет три натуральных делителя.

Изучением свойств простых чисел занимается теория чисел, а основная теорема арифметики устанавливает в ней их центральную роль: любое целое число, превышающее , либо является простым, либо может быть выражено произведением простых чисел, причём такое представление однозначно с точностью до порядка сомножителей[1]. Единицу не относят к простым числам, так как иначе указанное разложение становится неоднозначным[2]: .

Натуральные числа можно разделить на три класса: единица (имеет один натуральный делитель), простое число (имеет два натуральных делителя), составное число (имеет более двух натуральных делителей)[1]. Как простых, так и составных чисел бесконечно много.

Существуют различные алгоритмы проверки числа на простоту. Например, известный метод перебора делителей, в сравнении с другими примитивный и медленный.Перейти к разделу «#Тест простоты»

Простые числа широко используются в математике и смежных науках. Во многих алгоритмах информационных технологий, например в асимметричных криптосистемах, используются свойства факторизации целых чисел[4].