homechevron_rightУчебаchevron_rightМатематикаchevron_rightГеометрия

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

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

Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/3754/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).

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

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}.

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

Комментарии