Алгоритм, использующий разложение числа на простые множители

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

Наибольший общий делитель (НОД) двух целых чисел a и b – это наибольшее целое число, которое делит их оба.

Пример. НОД(30,18)=6.

Переборный алгоритм

Начинаем перебор с d – наименьшего из двух чисел. Это первый, очевидный «кандидат» на роль их наибольшего общего делителя. А затем, пока d не делит оба числа, уменьшаем его на единицу. Как только поделит – останавливаемся.

Procedure nod(a,b:Integer; Var d:Integer);

Begin

If a<b Then d:=a Else d:=b;

While Not((a Mod d=0)And(b Mod d=0)) Do d:=d-1;

End;

Обратимся к процедуре, допустим, с числами 30 и 18. Тогда на пути к ответу 6 ей придётся перебрать 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6.

Алгоритм, использующий разложение числа на простые множители

Прежде, чем сформулировать алгоритм рассмотрим несколько вспомогательных задач.

Натуральное число называется простым, если оно делится только на единицу и самого себя. Все другие натуральные числа, имеющие три и более делителей, называются составными. Единица не является ни простой, ни составной. Например, 17 – простое, а 91=7∙13 – составное.

Задача. Разработать функцию, проверяющую число на простоту. Необходимо проверять числа от 2 до x-1 на предмет того, являются они делителями числа x, или нет. Если «споткнулись» о делитель числа x, то x – составное, иначе – простое.

Function prime(x:Integer):Boolean;

Var i,g:Integer;

Begin

i:=2;

g:=x-1;

While (x Mod i<>0) And (i<=g) Do i:=i+1;

If i<=g Then prime:=False Else prime:=True;

End;

Вызываем функцию, например, для числа 13. Она перебирает числа 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, не находит среди них ни одного делителя 13 и поэтому сообщает, что оно простое.

Задача. Составить функцию, которая по данному простому числу находит следующее за ним простое число.

Увеличиваем на единицу данное простое число, пока не объявится следующее простое.

Function nextprime(p:Integer):Integer;

Begin

p:=p+1;

While Not(prime(p)) Do p:=p+1;

nextprime:=p;

End;

Известно, что любое натуральное число, большее 1, единственным образом раскладывается в произведение простых множителей.

Пример. 18200=182∙100=(91∙2)∙(25∙4)=(7∙13∙2)∙(5∙5∙2∙2). Всё, все множители простые. Группируем их и располагаем по возрастанию: 18200=2³∙5²∙7∙13.

Для хранения такого представления числа в памяти компьютера можно использовать два массива. В первом – простые числа. 2, 3, 5, 7, 11, 13, 17, 19,... в порядке возрастания. Во втором указываем, в какой степени входит простое число в разложение данного числа. Если не входит вообще, то степень считаем равной 0. Так представлением числа 18200 будет массив [3, 0, 2, 1, 0, 1]. Заметим, что простых чисел, больших 13, нет в разложении 18200, поэтому дальше в массиве идут только нули. Выписывать их незачем. Первый массив необязателен, если, например, мы используем функцию nextprime для нахождения следующего простого числа.

Задача. По данному числу найти его представление в виде произведения простых множителей.

Пусть x – наше число. Берём первое простое число p₁. Пока x делится на p₁, делим его на p₁. Попутно считаем, сколько таких делений произошло. Это будет первая степень в искомом представлении. Если же p₁ вообще не делит x, то степень равна 0.

Берём второе простое число p₂. Повторяем те же действия. Получаем вторую степень в искомом представлении. И так для каждого следующего простого числа.

Однажды число x станет равным 1. Не может не стать. На каждом шаге мы полностью избавляемся от очередного простого множителя в его разложении.

Procedure destroy (x:Integer; Var pr:mas; Var l:Integer); {x – число, которое раскладываем на простые множители. pr – массив, где храним представление. l – его длина.}

Var p,st:Integer;

Begin

l:=0; p:=2;

While x>1 Do Begin

st:=0;

While x Mod p=0 Do Begin

x:=x Div p;

st:=st+1;

end;

l:=l+1; pr[l]:=st;

p:=nextprime(p);

End;

End;

Задача. Дано представление числа в виде произведения простых множителей. Требуется найти само число.

Алгоритм очевиден. Рассматриваем друг за другом простые числа: 2, 3, 5, 7, 11, 13, 17, 19,... Возводим их в соответствующие степени, которые указаны в представлении, перемножаем. При этом простые числа с нулевыми степенями пропускаем.

Пример. [3, 0, 2, 1, 0, 1]=2³∙5²∙7∙13=18200.

Procedure build (pr:mas; l:Integer; Var x:Integer);

Var p,i:Integer;

Begin

p:=2; x:=1;

For i:=1 To l Do Begin

{Функция step возводит натуральное число в натуральную степень.}

If pr[i]>0 Then x:=x*step(p,pr[i]);

p:=nextprime(p);

End;

End;

Задача. Для двух чисел известны их представления в виде произведения простых множителей. Найти аналогичное представление для наибольшего общего делителя этих чисел.

Допустим, что известны такие представления. [3, 0, 2, 1, 0, 1] и [2, 1, 1, 2]. Это числа 2³∙5²∙7∙13=18200 и 2²∙3∙5∙7²=2940.

Наибольший общий делитель d строим только из общих «кирпичиков» двух чисел. Никакой не забываем и лишних не берём.

Так первые элементы представлений – 3 и 2. Это значит, что простая двойка входит в разложение первого числа в степени 3, а в разложение второго – в степени 2. Поэтому она обязана быть и в разложении d, в степени 2.

Вторые элементы – 0 и 1. Это значит, что простой тройки в разложении первого числа вообще нет. Не будет её и в разложении d.

Итак, представление для d определяем по правилу. Идём по представлениям чисел, пока одно из них не закончится, и на каждом шаге выбираем минимум из степеней.

Проверим, [2, 0, 1, 1]=2²∙5∙7=140. Верно.

Procedure nodpr (pr1,pr2:mas; l1,l2:Integer; Var pr:mas; Var l:Integer); {pr1, pr2 и pr – представления для двух чисел и их наибольшего общего делителя. l1,l2 и l – длины этих представлений.}

Var i:Integer;

Begin

If l1<l2 Then l:=la Else l:=lb;

For i:=1 To l Do

If pr1[i]<pr2[i] Then pr[i]:=pr1[i] Else pr[i]:=pr2[i];

End;

Вспомогательные задачи решены. Алгоритм поиска наибольшего общего делителя формулируется следующим образом.

Шаг 1. Находим представления чисел a и b в виде произведения простых множителей (дважды запускаем процедуру destroy).

Шаг 2. По найденным разложениям чисел a и b определяем разложение их наибольшего общего делителя (используем процедуру nodpr).

Шаг 3. Зная разложение наибольшего общего делителя на простые множители, вычисляем его значение (процедура build).

Алгоритм Евклида «c вычитанием»

Пусть a и b – целые числа, тогда верны следующие утверждения:

a) все общие делители пары a и b являются также общими делителями пары а–b и b;

b) и наоборот, все общие делители пары a–b и b являются также общими делителями пары a и b;

c) НОД(a, b)=НОД(a–b, b);

d) НОД(a,0)=a.

Доказательство.

a) Если t – произвольный общий делитель a и b, то он делит и разность a-b. Действительно, из a=t·u и b=t·v следует, что a-b=t·u–t·v=t·(u–v). То есть t – также общий делитель а–b и b.

b) Обратно, если t – произвольный общий делитель a–b и b, то он делит и их сумму a-b+b=a. Это показывается аналогично. Поэтому t – также общий делитель а и b.

c) Делаем вывод, что множество общих делителей пары a и b совпадает с множеством делителей пары а–b и b. В частности, совпадают и наибольшие общие делители этих пар. Таким образом, любое из двух чисел можно заменить на их разность – и наибольший общий делитель при этом не изменится.

d) Наибольшее целое, на которое делится число a, есть само a. Число 0 делится вообще на любое целое число. Отсюда, наибольший общий делитель a и 0 равен a.

Доказанная формула c) позволяют свести вычисление наибольшего делителя одной пары чисел к вычислению наибольшего общего делителя другой пары. Числа в новой паре меньше. Очевидные формулы d) говорят нам, когда остановится.

Коротко алгоритм таков. Вычитаем из большего числа меньшее и заменяем большее на эту разность до тех пор, пока одно из чисел не станет нулевым. То, которое ненулевое – искомый наибольший общий делитель.

Пример. Пусть a=82 и b=60. НОД(82,60)= НОД(22,60)= НОД(22,38)= НОД(22,16)= НОД(6,16)= НОД(6,10)= НОД(6,4)= НОД(2,4)= НОД(2,2)= НОД(2,0)= 2.

Во-первых, при каждом переходе к новой паре чисел наибольший общий делитель не изменяется. Во-вторых, пара, где одно из чисел нулевое, обязательно объявится. Так как на каждом шаге одно из чисел уменьшается, причём они остаются положительными. Уменьшение не может продолжаться бесконечно.

Программная реализация.

Procedure Euclid (a,b: Integer; Var d: Integer);

Begin

While (a>0) And (b>0) Do

If a>b Then a:=a-b Else b:=b-a;

If a=0 Then d:=b Else d:=a;

End;

Заметим, что на предпоследнем шаге алгоритма, перед появлением нуля, оба числа равны. Иначе ноль не мог бы возникнуть. Зная это, упростим процедуру Euclid. Избавимся от последнего условия в ней.

Procedure Euclid (a,b: Integer; Var d: Integer );

Begin

While a<>b Do

If a>b Then a:=a-b Else b:=b-a;

d:=a;

End;

Естественно, что эта логика может быть представлена и в рекурсивном виде:

Procedure Euclid (a,b:Integer; Var d:Integer);

Begin

If a=b Then d:=a

Else If a>b Then Euclid(a-b,b,d) Else Euclid(a,b-a,d);

End;

Алгоритм Евклида «с делением»

Пусть a и b – целые числа, r – остаток от деления a на b. Тогда НОД(a, b)=НОД(b, r).

Эта формула также позволяет свести вычисление наибольшего общего делителя одной пары чисел к вычислению наибольшего общего делителя другой пары чисел. Формулировка нового алгоритма, доказательство и программная реализация аналогичны тем, которые приведены для алгоритма Евклида «с вычитанием».

Находим остаток при делении большего числа на меньшее и заменяем большее число остатком. Замены выполняются до тех пор, пока одно из чисел не станет нулевым. То, которое ненулевое – искомый наибольший общий делитель.

Пример. НОД(82,60)= НОД(22,60)= НОД(22,16)= НОД(6,16)= НОД(6,4)= НОД(2,4)= НОД(0,2)= 2.

Программная реализация.

Procedure Euclid (a,b: Integer; Var d: Integer);

Begin

While (a>0) And (b>0) Do

If a>b Then a:=a Mod b

Else b:=b Mod a;

If a=0 Then d:=b Else d:=a;

End;

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

Procedure Euclid (a,b:Integer; Var d:Integer);

Var r:Integer;

Begin

While b>0 Do Begin

r:=a Mod b;

a:=b; b:=r;

End;

d:=a;

End;

В таком виде алгоритм проще выполнять и вручную. Достаточно выписать цепочку остатков и взять последний остаток, не равный нулю: 82, 60, 22, 16, 6, 4, 2, 0.

Рекурсивная реализация алгоритма имеет вид:

Procedure Euclid (a,b:Integer; Var d:Integer);

Begin

If b=0 Then d:=a Else Euclid(b,a Mod b, d);

End;

Бинарный алгоритм Евклида

Доказательство достаточно очевидных утверждений:

a) НОД(2·a, 2·b)= 2·НОД(a, b);

b) НОД(2·a, 2·b+1)= НОД(a, 2·b+1);

c) НОД(2·a+1, 2·b+1)= НОД(a-b, 2·b+1);

позволяет построить еще один алгоритм нахождения наибольшего общего делителя – бинарный алгоритм.

Пример. Пусть a=180 и b=48. Работа алгоритма приведена в табл. 1.5.

Таблица 1.5

Программная реализация.

Procedure BinEuclid(a,b: Integer; Var d :Integer);

Begin

d:=1;

While (a Mod 2=0) And (b Mod 2=0) Do Begin

a:=a Div 2;

b:=b Div 2;

d:=d*2;

End;

While (a>0) And (b>0) Do Begin

While (a Mod 2=0) Do a:=a Div 2;

While (b Mod 2=0) Do b:=b Div 2;

If a>b Then a:=(a-b) Div 2 Else b:=(b-a) Div 2;

End;

If a=0 Then d:=d*b Else d:=d*a;

End;

Процедуру можно переписать и без использования операций деления и умножения на 2.

Procedure BinEuclid(a,b: Integer; Var d :Integer);

Begin

d:=0;

While (a And 1=0) And (b And 1=0) Do Begin

a:=a ShR 1;

b:=b ShR 1;

d:=d+1;

End;

While (a>0) And (b>0) Do Begin

While (a And 1=0) Do a:=a ShR 1;

While (b And 1=0) Do b:=b ShR 1;

If a>b Then a:=(a-b) ShR 1 Else b:=(b-a) ShR 1;

End;

If a=0 Then d:=b ShL d Else d:=a ShL d;

End;

Поиск по сайту: