Если у числа a нет простых делителей, то никакое кратное им число тоже не будет его делителем. Поэтому, чтобы узнать, простое ли число, достаточно проверить его делимость только на простые числа.
Можно сократить проверку ещё сильнее. Если a — составное, то a = bc, где b, c > 1, и квадраты b и c не могут одновременно быть больше a (иначе bc > a). Значит, у составного числа всегда есть делитель, отличный от 1, квадрат которого не больше самого числа.
Алгоритм ответа на вопрос «Является ли число a простым?»
- Выписать все простые числа, квадраты которых не больше a.
- Если a делится хотя бы на одно из выписанных чисел, то a — составное.
- Если a не делится ни на одно из выписанных чисел, то a — простое.
Пример. 113: простые числа с квадратом не больше 113 — это 2, 3, 5, 7 (11² = 121 > 113). На них 113 не делится, значит, 113 — простое.
Простых чисел бесконечно много. Предположим, что их конечное число: 2, 3, 5, …, p. Число a = 2 · 3 · 5 · … · p + 1 больше каждого из них, значит, составное. Но при делении на любое из наших простых чисел оно даёт остаток 1 — противоречие.