Факторизация целых чисел. Перебор делителей

Факторизация целых чисел методом перебора делителей.

Понадобилось тут научиться раскладывать целые числа на множители. Посколько числа предполагаются не сильно большие, то написал калькулятор разложения числа на множители методом перебора делителей. Описание метода — под калькулятором.

PLANETCALC, Факторизация целых чисел. Перебор делителей

Факторизация целых чисел. Перебор делителей

Факторизация
 
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Факторизация целых чисел

Факторизацией натурального числа называется его разложение в произведение простых множителей.

Не будет далеко уходить от Википедии, и скажем, что метод перебора возможных делителей, или метод пробного деления — наиболее тривиальный алгоритм факторизации, с вычислительной сложностью \Theta(N^{1/2}log(N)), где 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 также будет делителем, причём один из этих делителей не превосходит \sqrt{n}.

По-моему, достаточно исчерпывающе.

Ссылка скопирована в буфер обмена
PLANETCALC, Факторизация целых чисел. Перебор делителей

Комментарии