Перебор делителей считается трудоёмким процессом при больших числах, потому что время работы такого алгоритма составляет порядка О(n1/2), то есть растёт экспоненциально относительно битовой длины n. 2

Обычно перебор делителей заключается в переборе всех целых чисел от 2 до квадратного корня из тестируемого числа n и в вычислении остатка от деления n на каждое из этих чисел. 3