Просто́е число (Р) – натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя – единицу и самого себя (Р). Последовательность простых чисел бесконечна и начинается так: 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199… Элементарный, но медленный метод проверки простоты заданного натурального числа N известен как перебор делителей, который состоит из проверки того, делится ли нацело (без остатка) число N хоть на одно из первых натуральных чисел 2, 3, 4, 5, 6, ...

Простые числа — это такие натуральные числа, которые делятся только на единицу и на самих себя (имеют только два делителя). Все остальные натуральные числа, которые имеют более двух делителей, называются составными. Единицу не относят ни к простым, ни к составным числам, т. к. у неё только один делитель — единица. Самое маленькое (и первое) простое число — 2. Следующие по возрастанию простые числа: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ... Ещё Евклид доказал, что множество простых чисел неограниченно,...