Перебор делителей
Из Википедии, свободной энциклопедии
Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путём полного перебора всех возможных потенциальных делителей.
Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число i равен 0, то i является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на i и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел n объявляется простым[1].
Для ускорения перебора часто не проверяются чётные делители, кроме числа 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. Сложность данного алгоритма
![{\displaystyle O(n^{1/2})={\sqrt[{2}]{n}}}](http://wikimedia.org/api/rest_v1/media/math/render/svg/d197f5234ae923d41ba038702578c5eb08c59f35)
Для иллюстрации проведем перебор делителей числа n = 29. i — возможные делители n.
![{\displaystyle [n^{1/2}]=5}](http://wikimedia.org/api/rest_v1/media/math/render/svg/41f9043a9dbbd56e524b5521ad4868cc73b73800)
| i | n % i |
|---|---|
| 2 | 1 |
| 3 | 2 |
| 4 | 1 |
| 5 | 4 |
Так как ни один из остатков деления 29 не равен 0, то 29 объявляется простым.
Пусть теперь n = 7399, тогда[2]
![{\displaystyle [n^{1/2}]=86}](http://wikimedia.org/api/rest_v1/media/math/render/svg/05573d4c9152d5ece37459066e8c00cdf62035ec)
| i | n % i |
|---|---|
| 2 | 1 |
| 3 | 1 |
| 4 | 3 |
| 5 | 4 |
| 6 | 1 |
| 7 | 0 |
Так как остаток деления 7399 на 7 равен 0, то 7399 не является простым.
В практических задачах данный алгоритм применяется редко ввиду его большой вычислительной сложности, однако его применение оправдано в случае, если проверяемые числа относительно невелики, так как данный алгоритм довольно легко реализуем[1].
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
