Чтобы проверить, простое ли число n, делят его на простые числа 2, 3, 5, 7, 11, … — но только на те, квадрат которых не больше n. Если ни одно не делит n, число простое: у составного числа есть простой делитель, не больший √n.
Пример. 221: 15² = 225 > 221, проверяем 2, 3, 5, 7, 11, 13: 221 = 13 · 17 — составное. 199: на 2, 3, 5, 7, 11, 13 не делится (14² = 196 ≤ 199, 17² > 199) — простое.
Часто хватает признаков делимости: 1 000 101 делится на 3 (сумма цифр 3), 4 035 — на 5, значит, оба составные.