Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путём полного перебора всех возможных потенциальных делителей.
Описание алгоритма
Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число i равен 0, то i является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на i и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел n объявляется простым.
Для ускорения перебора часто не проверяются чётные делители, кроме числа 2, а также делители, кратные трём, кроме числа 3. При этом тест ускоряется в три раза, так как из каждых шести последовательных потенциальных делителей необходимо проверить только два, а именно вида 6·k±1, где k — натуральное число.
Данный алгоритм является ресурсоемким при проверке больших чисел на простоту, но для его ускорения можно прибегнуть к следующим методам оптимизации. Для объяснения возьмем три последовательных числа (n-1, n, n+1). Предположим, что число n — простое, не равное двум. Так как n — простое, то слева и справа от него будут стоять числа, кратные двум, а исходя из того, что мы рассматриваем тройку подряд идущих чисел, среди них обязательно найдётся число, кратное трем. Тогда число n-1 и n+1 кратны двум, и одно из них кратно трем; следовательно, одно из этих чисел будет кратно шести. Теперь мы можем сказать, что простое число, большее трех, всегда будет стоять рядом с числом, кратным шести. Оптимизируя наш алгоритм, мы можем изначально проверить окрестность большого числа N, а именно N-1 и N+1, на кратность 6, и после этого запустить алгоритм проверки на простоту. Данный метод можно использовать и на задачах, связанных с отрезком чисел, и перебирать только те, которые стоят рядом с числом, кратным шести.
Скорость Худший случай, если перебор придется проводить от 2 до корня из n. Сложность данного алгоритма
Пример Для иллюстрации проведем перебор делителей числа n = 29. i — возможные делители n.
in % i21324154
Так как ни один из остатков деления 29 не равен 0, то 29 объявляется простым.
Пусть теперь n = 7399, тогда
in % i213143546170 Так как остаток деления 7399 на 7 равен 0, то 7399 не является простым.
Практическое применение В практических задачах данный алгоритм применяется редко ввиду его большой вычислительной сложности, однако его применение оправдано в случае, если проверяемые числа относительно невелики, так как данный алгоритм довольно легко реализуем.
См. также
Решето Эратосфена Решето Сундарама Решето Аткина Тест простоты
Примечания
Литература
Ссылки Javascript Prime Factor Calculator using trial division . Способен обрабатывать числа до 9×1015
Категория:Алгоритмы факторизации Категория:Тесты простоты