Перебор делителей

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание алгоритма[править | править вики-текст]

Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число i равен 0, то i является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на i и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.[1]

Для ускорения перебора часто не проверяются чётные делители, кроме числа 2, а также делители кратные трём, кроме числа 3. При этом тест ускоряется в три раза, так как из каждых шести последовательных потенциальных делителей необходимо проверить только два, а именно вида 6·k±1, где k — натуральное число.

Алгоритм "Перебор делителей"

Скорость[править | править вики-текст]

Худший случай, если перебор придется проводить от 2 до корня из n. Сложность данного алгоритма

O(n^{1/2})[2]

Пример[править | править вики-текст]

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

[n^{1/2}] = 5

i n % i
2 1
3 2
4 1
5 4

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

Пусть теперь n = 7399, тогда[3]

[n^{1/2}] = 86 

i n % i
2 1
3 1
4 3
5 4
6 1
7 0

Так как остаток деления 7399 на 7 равен 0, то 7399 не является простым.

Практическое применение[править | править вики-текст]

В практических задачах данный алгоритм применяется редко ввиду его большой вычислительной сложности, однако его применение оправдано в случае, если проверяемые числа относительно невелики, так как данный алгоритм довольно легко реализуем.[1]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Lindsay N. Childs. A Concrete Introduction to Higher Algebra. — 3rd ed. — New York, 2009. — С. 117-118. — 603 с.
  2. Факторизация.
  3. Richard Crandall; Carl Pomerance. Prime numbers. A computational perspective. — 2nd ed. — New York, 2005. — С. 117-119. — 597 с.


Литература[править | править вики-текст]

  • Lindsay N. Childs. A Concrete Introduction to Higher Algebra. — 3rd ed. — New York, 2009. — 603 с.
  • Richard Crandall; Carl Pomerance. Prime numbers. A computational perspective. — 2nd ed. — New York, 2005. — 597 с.

Внешние ссылки[править | править вики-текст]