94.19.10.96: /* Описание алгоритма */ Если рассмотреть тройку чисел (1, 2, 3), которая подходит под описание "(n-1, n, n+1), где n - простое", то утверждение дальше ("Так как n — простое, то слева и справа от него будут стоять числа, кратные двум") неверно, так как 1 и 3 не кратны двум.

2025-12-05T20:00:19Z

Описание алгоритма: Если рассмотреть тройку чисел (1, 2, 3), которая подходит под описание "(n-1, n, n+1), где n - простое", то утверждение дальше ("Так как n — простое, то слева и справа от него будут стоять числа, кратные двум") неверно, так как 1 и 3 не кратны двум.

Новая страница

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

== Описание алгоритма ==
[[Файл:Trial division.jpg|thumb|Алгоритм «Перебор делителей»]]
Обычно перебор делителей заключается в переборе всех [[целое число|целых]] (как вариант: [[простое число|простых]]) чисел от 2 до [[квадратный корень|квадратного корня]] из факторизуемого числа ''n'' и в вычислении [[деление с остатком|остатка от деления]] ''n'' на каждое из этих чисел. Если остаток от деления на некоторое число ''i'' равен 0, то ''i'' является делителем ''n''. В этом случае либо ''n'' объявляется составным, и алгоритм заканчивает работу (если тестируется простота ''n''), либо ''n'' сокращается на ''i'' и процедура повторяется (если осуществляется факторизация ''n''). По достижении квадратного корня из ''n'' и невозможности сократить ''n'' ни на одно из меньших чисел ''n'' объявляется простым{{sfn|Childs|2009|pp=117-118}}.

Для ускорения перебора часто не проверяются чётные делители, кроме числа 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''. Сложность данного алгоритма

: <math>O(n^{1/2})=\sqrt[2]{n}</math>

== Пример ==
Для иллюстрации проведем перебор делителей числа ''n'' = 29. ''i'' — возможные делители ''n''.

<math>[n^{1/2}] = 5</math>
{| class="wikitable"
!i
!n % i
|-
|2
|1
|-
|3
|2
|-
|4
|1
|-
|5
|4
|}

Так как ни один из остатков деления 29 не равен 0, то 29 объявляется простым.

Пусть теперь ''n'' = 7399, тогда{{sfn|Crandall, Pomerance|2005|pp=117-119}}

<math>[n^{1/2}] = 86</math>
{| class="wikitable"
!i
!n % i
|-
|2
|1
|-
|3
|1
|-
|4
|3
|-
|5
|4
|-
|6
|1
|-
|7
|0
|}
Так как остаток деления 7399 на 7 равен 0, то 7399 не является простым.

== Практическое применение ==
В практических задачах данный [[алгоритм]] применяется редко ввиду его большой [[Вычислительная сложность|вычислительной сложности]], однако его применение оправдано в случае, если проверяемые числа относительно невелики, так как данный алгоритм довольно легко реализуем{{sfn|Childs|2009|pp=117-118}}.

== См. также ==
{{Викиучебник|Программные реализации перебора делителей|Программные реализации перебора делителей}}
* [[Решето Эратосфена]]
* [[Решето Сундарама]]
* [[Решето Аткина]]
* [[Тест простоты]]

== Примечания ==
{{примечания}}

== Литература ==
* {{книга |автор= Lindsay N. Childs | название=A Concrete Introduction to Higher Algebra |ссылка= https://archive.org/details/concreteintroduc0000chil_t3a9 |издание=3rd ed |место=New York |год=2009 |allpages=603 |ref=Childs}}
* {{книга |автор= Richard Crandall, Carl Pomerance | название=Prime numbers. A computational perspective |ссылка= https://archive.org/details/primenumberscomp0002cran |издание=2nd ed |место=New York |год=2005 |allpages=597 |ref=Crandall, Pomerance}}

== Ссылки ==
* [http://www.se16.info/js/factor.htm Javascript Prime Factor Calculator using trial division] {{Wayback|url=http://www.se16.info/js/factor.htm |date=20150110203651 }}. Способен обрабатывать числа до 9×10<sup>15</sup>
* {{Cite web|url = http://ru.math.wikia.com/wiki/Факторизация|title = Факторизация|author = |date = |publisher = wikia|access-date = 2022-03-29|archive-date = 2018-12-28|archive-url = https://web.archive.org/web/20181228053012/http://ru.math.wikia.com/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F|url-status = live}}

{{Нет источников |дата=2014-10-19}}

[[Категория:Алгоритмы факторизации]]
[[Категория:Тесты простоты]]

Перебор делителей - История изменений