Факторизация перебором делителей

Разложение числа на простые множители называется факторизацией.

Факторизация целых чисел обеспечивается основной теоремой арифметики:

Каждое натуральное число n>1 можно представить в виде n=p1∗p2∗p3∗…∗pk, где p1,p2,p3,…pk— простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

Факторизация числа методом перебора делителей производится почти так же, как и тест простоты числа методом перебора делителей. Производится перебор всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае n сокращается на m и процедура повторяется. По достижении квадратного корня из оставшегося числа и невозможности сократить его ни на одно из меньших чисел, оно объявляется простым и также приписывается к простым сомножителям исходного числа n.

Факторизация целых чисел для больших чисел является сложной задачей. Её сложность лежит в основе некоторых алгоритмов безопасности с открытым ключом шифрования, например, алгоритма RSA.

ФАКТОРИЗАЦИЯ ПЕРЕБОРОМ ДЕЛИТЕЛЕЙ НА PYTHON

def factorize(n):
divisor = 2
while divisor ** 2 <= n:
if n % divisor == 0:
n //= divisor
print(divisor)
else:
divisor += 1
if n!= 1:
print(n)

n = int(input())
factorize(n)

 

ФАКТОРИЗАЦИЯ ПЕРЕБОРОМ ДЕЛИТЕЛЕЙ НА PASCAL

procedure factorize(n: longint);

var

divisor: longint;

begin

divisor:= 2;

while divisor * divisor <= n do

if n mod divisor = 0 then begin

n:= n div divisor;

writeln(divisor);

end

else

inc(divisor);

if n <> 1 then

writeln(n);

end;

var

n: longint;

begin

readln(n);

factorize(n);

end.

Разложение числа на множители в Python

Основная теорема арифметики гласит, что разложение числа на простые множители существует и единственно. Решение этой задачи оформим в виде функции, которая по заданному числу n возвращает список его простых делителей с учетом кратности.

Алгоритм разложения числа на множители похож на алгоритм проверки числа на простоту. Будем проверять делимость данного числа n на натуральные числа подряд, начиная с числа 2. Если мы находим делитель числа n, то будем делить число n на данный делитель, пока число делится на него и добавлять делитель в список простых делителей.

Перебор также необходимо продолжать до n√. Если после окончания этого алгоритма число n не станет равно 1, то оставшееся значение также является простым, так как не делится ни на одно число, не превосходящее корня из оставшегося значения, поэтому его нужно добавить к списку простых делителей:

def Factor(n):

Ans = []

d = 2

while d * d <= n:

if n % d == 0:

Ans.append(d)

n //= d

else:

d += 1

if n > 1:

Ans.append(n)

return Ans

Сложность такого алгоритма, как и сложность алгоритма проверки числа на простоту, O(n√).

Алгоритм Евклида: Python

Рассмотрим задачу нахождения наибольшего общего делителя двух натуральных чисел. Постановка задачи — даны два натуральных числа a и b, необходимо найти такое наибольшее число d, которое является делителем каждого из этих чисел.

Задачу можно решать разными способами. Наивный алгоритм — будем перебирать все числа от 1 до min(a,b), будем проверять делимость чисел a и b на проверяемое число, выберем наибольшее число, на которое делятся и a, и b. Такой алгоритм будет имеет сложность O(min(a,b)).

Можно оптимизировать перебор, например, перебирать не все числа до min(a,b), а только делители одного из чисел (a или b). Это можно организовать перебирая числа до min(a,b)−−−−−−−√, если использовать идеи, аналогичные оптимизации алгоритма проверки числа на простоту, то есть алгоритм будет иметь сложность O(min(a,b)−−−−−−−√).

Гораздо более эффективно можно решить эту же задачу, если использовать алгоритм Евклида. Он основан на следующем свойстве (обозначим наибольший общий делитель чисел a и b как НОД(a, b)):

НОД(a, b) = НОД(a - b, b)

Свойство легко доказать, если заметить, что любой общий делитель чисел a и b также является общим делителем чисел a - b и b, и наоборот, т. е. для пар чисел (a, b) и (a - b, b) совпадают множества общих делителей, и, значит, и наибольший общий делитель.

Это позволяет написать рекурсивный алгоритм (название gcd есть аббревиатура от Greatest Common Divisor):

def gcd(a, b):
if a == 0 or b == 0:
return max(a, b)
else:
if a > b:
return gcd(a - b, b)
else:
return gcd(a, b - a)

Этот алгоритм использует указанные рекуррентные соотношения до тех пор, пока одно из чисел не станет равно 0 (иногда используют другое условие окончания алгоритма — числа a и b станут равны), в этом случае возвращается значение другого числа.

Этот же алгоритм можно записать при помощи цикла while, без рекурсии:

def gcd(a, b):
while a!= 0 and b!= 0:
if a > b:
a = a - b
else:
b = b — a
return max(a, b)

Записанный в таком виде алгоритм неэффективен, так как многократно использует вычитания. Например, если взять a=10∗∗9+2, b=2, то алгоритм выполнит 500 миллионов вычитаний для получения вполне очевидного результата. Чтобы оптимизировать алгоритм необходимо понять, что многократное вычитание из большего числа меньшего закончится на числе, которое является остатком от деления двух первоначальных чисел. То есть в каждом из этих алгоритмов можно заменить операцию вычитания на взятие остатка:

def gcd(a, b):
if a == 0 or b == 0:
return max(a, b)
else:
if a > b:
return gcd(a % b, b)
else:
return gcd(a, b % a)

или

def gcd(a, b):
while a!= 0 and b!= 0:
if a > b:
a = a % b
else:
b = b % a
return max(a, b)

Но алгоритм Евклида можно записать и еще проще. Давайте будем считать, что a≥b. Тогда после замены a=a%b результат этой операции станет меньше чем b, то есть теперь a<b. Чтобы вернуть свойство a≥b нужно поменять a и b местами, что удобно делать при помощи кортежей:

def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)

или

def gcd(a, b):
while b!= 0:
a, b = b, a % b
return a

Таким образом, в этом алгоритме поддерживается два инварианта: a≥b и НОД(a,b) не меняется. Несложно заметить, что алгоритм будет корректно работать и в случае, когда a<b, тогда на первом же шаге значения a и b будут просто поменяны местами.

Можно показать, что наибольшее количество операций алгоритм Евклида будет выполнять, когда на вход ему даны два числа, являющиеся соседними членами ряда Фибоначчи, то есть ряда 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181 и т. д. Известно, что n-й член последовательности Фибоначчи можно вычислить по формуле

Fn=(1+5√2)n−(1−5√2)n5√, то есть Fn≈15√(1+5√2)n. Таким образом, сложность алгоритма Евклида: O(logmin(a,b)).