Как правило, это удивляет нематематиков, — ведь в школе учат проверять число на простоту тем же методом, что и искать его простые множители: перебором всех возможных делителей.

Объединив оба утверждения, несложно сделать вывод, что любое число есть результат перемножения простых множителей и что их набор единственный, если не брать во внимание порядок записи.

Как ни удивительно, определить, является ли данное число простым, относительно несложно, но если число составное, то отыскать его простые множители часто намного труднее.

Даже этот знакомый процесс заводит нас на глубину сразу же, как только мы начинаем задавать вопросы о по-настоящему эффективных методах поиска простых множителей конкретного числа.

Начинается она с установления некоторых базовых понятий: в частности, концепции разложения на простые множители — как представить заданное число в виде произведения простых чисел.

В то же время мы угодим в тупик, если попытаемся выяснить, какие два простых множителя дают N при умножении.

Мы можем добавить его в наш перечень и наштамповать так ещё много чисел — либо простых, либо разложимых на простые множители.

Стало быть, или это число само простое, или его можно разложить на простые множители, не входящие в наш перечень.