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

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

Эта страница существует благодаря следующим персонам

Timur

Timur

Создан: 2014-07-18 14:03:33, Последнее изменение: 2022-03-08 16:34:57

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

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, Факторизация целых чисел. Перебор делителей

Комментарии