Как определить простоту числа методом пробного деления?

Метод пробного деления (перебор делителей) — алгоритм тестирования простоты числа путём полного перебора всех возможных потенциальных делителей. ru.wikipedia.org

Алгоритм: ru.wikipedia.org

1. Перебрать все целые (как вариант: простые) числа от 2 до квадратного корня из проверяемого числа n. ru.wikipedia.org
2. Вычислить остаток от деления n на каждое из этих чисел. ru.wikipedia.org
3. Если остаток от деления на некоторое число i равен 0, то i является делителем n. ru.wikipedia.org
4. В этом случае либо n объявляется составным, и алгоритм заканчивает работу, либо n сокращается на i и процедура повторяется. ru.wikipedia.org
5. По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел n объявляется простым. ru.wikipedia.org

Пример: нужно определить, является ли простым число 81. www.sravni.ru Для этого сначала узнают значение корня из 81 (√81 = 9). www.sravni.ru Значит, нужно попробовать поделить 81 на простые числа от 2 до 9, это 2, 3, 5 и 7: www.sravni.ru

• 81 / 2 = 40,5, дробное число, не подходит; www.sravni.ru
• 81 / 3 = 27, целое число. www.sravni.ru

Ответ: 81 — составное число, потому что оно делится без остатка не только на 1 и на само себя. www.sravni.ru

Для ускорения перебора часто не проверяют чётные делители, кроме числа 2, а также делители, кратные трём, кроме числа 3. ru.wikipedia.org

Этот алгоритм является ресурсоёмким при проверке больших чисел на простоту, поэтому в практических задачах его применяют редко. ru.wikipedia.org