Перебор делителей

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

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


 Обычно перебор делителей заключается в переборе всех целых (как вариант:простых) чисел от 2 до квадратного корня из факторизуемого числаn и в вычислении остатка от деления n на каждое из этихчисел. Если остаток от деления на некоторое число i равен 0, тоi является делителем n. В этом случае либо nобъявляется составным, и алгоритм заканчивает работу (если тестируетсяпростота n), либо n сокращается на i и процедураповторяется (если осуществляется факторизация n). По достиженииквадратного корня из n и невозможности сократить n ни наодно из меньших чисел n объявляется простым.
 Для ускорения перебора часто не проверяются чётные делители, кроме числа2, а также делители, кратные трём, кроме числа 3. При этом тестускоряется в три раза, так как из каждых шести последовательныхпотенциальных делителей необходимо проверить только два, а именно вида6·k±1, где k — натуральное число.

Скорость


 Худший случай, если перебор придется проводить от 2 до корня изn. Сложность данного алгоритма

O(n1/2)

Пример


 Для иллюстрации проведем перебор делителей числа n = 29.i — возможные делители n.
[n1/2]=5
in
21
31
43
54
61
70

 Так как остаток деления 7399 на 7 равен 0, то 7399 не является простым.

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


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