Факторизация целых чисел. Перебор делителей
Факторизация целых чисел методом перебора делителей.
Эта страница существует благодаря следующим персонам
 | Timur
|
Понадобилось тут научиться раскладывать целые числа на множители. Посколько числа предполагаются не сильно большие, то написал калькулятор разложения числа на множители методом перебора делителей. Описание метода — под калькулятором.
Факторизация целых чисел. Перебор делителей
Факторизация целых чисел
Факторизацией натурального числа называется его разложение в произведение простых множителей.
Не будет далеко уходить от Википедии, и скажем, что метод перебора возможных делителей, или метод пробного деления — наиболее тривиальный алгоритм факторизации, с вычислительной сложностью , где N — число, подлежащее факторизации.
Далее описание, которое можно прочитать по ссылке на Википедию выше:
Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на m и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.
Для ускорения перебора часто не проверяются чётные делители, кроме числа 2, а также делители кратные трём, кроме числа 3. При этом тест ускоряется в три раза, так как из каждых шести последовательных потенциальных делителей необходимо проверить только два, а именно вида 6·k±1, где k — натуральное число.
Почему квадратный корень из n?
Опять же, из Википедии: Легко заметить, что если у n есть некоторый делитель p, то n/p также будет делителем, причём один из этих делителей не превосходит .
По-моему, достаточно исчерпывающе.
Комментарии