Суть теории простых чисел заключается в изучении свойств натуральных чисел, имеющих ровно два различных натуральных делителя: единицу и само себя. 45

Все составные числа состоят из простых и могут быть разложены на их произведения. 3 В этом смысле простые числа являются «строительными блоками» или «фундаментальными элементами» чисел. 3

Некоторые аспекты теории простых чисел:

• Проверка числа на простоту. 4 Самый очевидный способ — перебрать все числа, меньшие него, и проверить, являются ли они его делителями. 4 Достаточно проверять делители только до квадратного корня из данного числа. 4
• Основная теорема арифметики. 25 Утверждает, что любое разложение на простые числа будет тождественным с точностью до порядка делителей. 5
• Количество простых чисел бесконечно. 3 Это доказал ещё Евклид в 300 году до нашей эры. 3

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