Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.

Описание алгоритма

Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня^[1] из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на m и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.

Практическое применение

В практических задачах данный алгоритм применяется редко ввиду его большой асимптотической сложности (в О-нотации), однако его применение оправдано в случае, если проверяемые числа относительно невелики, так как данный алгоритм довольно легко реализуем.

Примечания