Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путём полного перебора всех возможных потенциальных делителей.
Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число i равен 0, то i является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на i и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел n объявляется простым[1].
Для ускорения перебора часто не проверяются чётные делители, кроме числа 2, а также делители, кратные трём, кроме числа 3. При этом тест ускоряется в три раза, так как из каждых шести последовательных потенциальных делителей необходимо проверить только два, а именно вида 6·k±1, где k — натуральное число.
Худший случай, если перебор придется проводить от 2 до корня из n. Сложность данного алгоритма
Для иллюстрации проведем перебор делителей числа n = 29. i — возможные делители n.
i | n % i |
---|---|
2 | 1 |
3 | 2 |
4 | 1 |
5 | 4 |
Так как ни один из остатков деления 29 не равен 0, то 29 объявляется простым.
Пусть теперь n = 7399, тогда[2]
i | n % i |
---|---|
2 | 1 |
3 | 1 |
4 | 3 |
5 | 4 |
6 | 1 |
7 | 0 |
Так как остаток деления 7399 на 7 равен 0, то 7399 не является простым.
В практических задачах данный алгоритм применяется редко ввиду его большой вычислительной сложности, однако его применение оправдано в случае, если проверяемые числа относительно невелики, так как данный алгоритм довольно легко реализуем[1].
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .