В чем заключается метод перебора делителей при факторизации целых чисел?

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

Суть метода заключается в следующем: ru.wikipedia.org

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

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