Перебор делителей
Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.
Описание алгоритма
Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня[1] из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на m и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.
Для ускорения перебора часто не проверяются чётные делители, кроме числа 2, а также делители кратные трём, кроме числа 3. При этом тест ускоряется в три раза, так как из каждых шести последовательных потенциальных делителей необходимо проверить только два, а именно вида 6·k±1, где k — натуральное число.
Скорость
Худший случай, если перебор придется проводить от 2 до корня из n. Сложность данного алгоритма
Пример
Для иллюстрации проведем перебор делителей числа ]n = 29. i возможные делители n.
![{\displaystyle [n^{1/2}]=5}](https://wikimedia.org/ruwiki/api/rest_v1/media/math/render/svg/41f9043a9dbbd56e524b5521ad4868cc73b73800)
| i | n % i |
|---|---|
| 2 | 1 |
| 3 | 2 |
| 4 | 1 |
| 5 | 4 |
Так как ни один из остатков деления 29 не равен 0, то 29 объявляется простым.
Пусть теперь n = 7399, тогда[3]
![{\displaystyle [n^{1/2}]=86}](https://wikimedia.org/ruwiki/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 не является простым.
Практическое применение
В практических задачах данный алгоритм применяется редко ввиду его большой вычислительной сложности, однако его применение оправдано в случае, если проверяемые числа относительно невелики, так как данный алгоритм довольно легко реализуем.
См. также
Примечания
- ↑ Легко заметить, что если у n есть некоторый делитель p, то n/p также будет делителем, причём один из этих делителей не превосходит
- ↑ Факторизация.
- ↑ Richard Crandall, Carl Pomerance. Prime numbers. A computational perspective.. — 2nd ed.. — New York: Springer, 2005. — С. 118-119. — 597 с. — ISBN 0-387-25282-7.
 | Это заготовка статьи по математике. Помогите Википедии, дополнив её. |
 | Для улучшения этой статьи желательно:
|
Литература
- Crandall, Richard. Prime numbers. A computational perspective / Richard Crandall, Carl Pomerance. — 2nd. — New York, NY : Springer-Verlag, 2005. — ISBN 0-387-25282-7.
Внешние ссылки
- Javascript Prime Factor Calculator using trial division. Способен обрабатывать числа до 9×1015