Как найти наибольший делитель числа паскаль

Приветствуем читателей и посетителей нашего сайта! Сегодня на learnpascal.ru открывается новая рубрика — Алгоритмы. В этой рубрике мы с вами будем разбирать различные алгоритмы, а также их реализацию на Паскале.

Для освоения материала сегодняшнего урока вам понадобится знание циклов и ветвлений.

Сегодня мы рассмотрим три алгоритма(из пяти) на нахождение наибольшего общего делителя двух целых чисел, два из которых непосредственно связывают с именем Евклида. Еще два мы рассмотрим в следующей части.
Наибольший общий делитель (НОД) двух чисел a и b — наибольшее целое число, которое делит их оба.
Пример: НОД(25, 5) = 5; НОД(12, 18) = 6.

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

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

var
  a, b, d: integer;

begin
  write('Введите два числа: ');
  readln(a, b);
  if a < b then d := a + 1 else d := b + 1; 
  {так как мы используем цикл с постусловием, 
  необходимо минимальное значение увеличить на один,
  иначе цикл repeat, в силу своих конструктивных особенностей,
  не учтет это минимальное число  
  и не сделает его кандидатом в НОД. Например, 5 и 25.}
  repeat d := d - 1
  until (a mod d = 0) and (b mod d = 0);
  write('NOD = ', d)
end.

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

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

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

1. Все общие делители пары a и b являются также общими делителями пары a — b, b;
2. И наоборот, все общие делители пары a — b и b являются также общими делителями пары a и b;
3. НОД(A,  B) = НОД(A — B, B), если A > B;
4. НОД(A, 0) = A.

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

1. Если t — произвольный общий делитель a и b, то он делит и разность a — b. Действительно, из a = t * u и b = t * v следует, что a — b = t * u — t * v = t * (u — v). То есть t — также общий делитель а — b и b.
2. Обратно, если t — произвольный делитель общий делитель a — b и b, то он делит и их сумму a — b + b = a. Это можно доказать аналгично предыдущему. Поэтому t — также общий делитель a и b.
3. Делаем вывод, что множество общих делителей a и b совпадает с множеством делителей a — b и b. В частности, совпадают и наибольшие общие делители этих пар.
4. Наибольшее целое, на которое делится число a, есть само число а. Число 0 делится на любое число. Отсюда наибольший общий делитель а и 0 равен а.

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

Вкратце алгоритм Евклида «с вычитанием» будет таким. Вычитаем из большего числа меньшее и заменяем большее на разность до тех пор, пока одно из чисел не обратится в нуль. Тогда оставшееся ненулевое число — наибольший общий делитель.

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

На предпоследнем шаге алгоритма, перед появлением 0, оба числа равны, иначе не мог возникнуть 0. Поэтому мы будем извлекать НОД именно в этот момент.

Блок — схема алгоритма Евклида «с вычитанием»

Программа

var
  a, b: integer;

begin
  write('a = '); 
  readln(a);
  write('b = ');
  readln(b);
  while a <> b do 
    if a > b then 
      a := a - b 
    else 
      b := b - a;
  writeln('NOD = ', a);
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.

var
  a, b: integer;

begin
  write('a = ');
  readln(a);
  write('b = ');
  readln(b);
  while (a <> 0) and (b <> 0) do
    if a >= b 
    then 
      a := a mod b 
    else 
      b := b mod a;
  write(a + b)
end.

На сегодня все! Еще несколько модификаций алгоритма Евклида и способов нахождения НОД вы узнаете на следующих уроках.

Приведем 3 программы поиска наибольшего общего делителя двух натуральных чисел, основанных на:

• алгоритме Евклида
• перебора возможных делителей числа
• разложения чисел на простые множители

Что такое наибольший общий делитель двух натуральных чисел m и n, или НОД(m, n)

НОД двух натуральных чисел – это такое наибольшее натуральное число, которое одновременно делит без остатка оба этих числа.

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

Евклид – древнегреческий математик, геометр, автор первого из дошедших до нас теоретических трактатов по математике.

Алгоритм Евклида – один из наиболее ранних численных алгоритмов в истории. Евклид впервые дал описание этого алгоритма в книгах «Начала». Изначально этот алгоритм назывался «взаимным вычитанием», так как его принцип заключался в последовательном вычитании из большего числа меньшего, пока в результате не получится ноль.

Сформулируем алгоритм

Пусть даны два натуральных числа m и n. Пока числа m и n не равны (или их разница не равна 0), большее число заменить их разницей. В качестве ответа взять любое из чисел.

Пример:

Пусть m = 12, n = 18

12<>18, n = 18 – 12 = 6

12<>6, m = 12 – 6 = 6

6<>6, НОД(12, 18) = 6

Программа на языке программирования Паскаль (алгоритм Евклида)

var m, n:integer;

begin

  writeln(‘Введите два натуральных числа m и n:’);  

  readln(m,n);

  while m<>n do

  begin

    if m>n then m:=m-n

           else n:=n-m;

  end;

  writeln(‘НОД(m,n): ‘,m);

end.

Результат запуска программы

Перебор возможных делителей числа

Будем использовать алгоритм, разобранный ранее в этом блоге.

Запустим цикл for с счетчиком k от 1 до n, будем проверять условие: если число n делится на значение счетчика k без остатка (n mod k = 0), то значение счетчика k – это делитель числа n, значение k можно вывести на экран или сохранить в отдельной переменной.

Поскольку нам нужен наибольший общий делитель чисел m и n, поэтому запустим цикл до минимального из чисел m и n (другое будет лишним), и будем проверять условие: если число m делится на значение счетчика цикла k без остатка и число n делится на значение счетчика цикла k без остатка одновременно (воспользуемся операцией and), это и будет их общий делитель.

Программа на языке программирования Паскаль (перебор возможных делителей числа)

var m, n, k, p:integer;

begin

  writeln(‘Введите два натуральных числа m и n:’);

  readln(m,n);

  for k:=1 to min(m,n) do 

  begin

    if (m mod k = 0) and (n mod k=0) then p:=k;

  end;

  writeln(‘НОД(m,n): ‘,p);

end.

Функция min будет работать в PascalABC.NET, в случае использования другой среды, нужно до цикла определить наибольшее число из m и n.

Разложение чисел на простые множители

Ранее мы разбирали алгоритм разложения натурального числа на простые множители. 

Как связаны простые множители числа и НОД. Приведем пример.

Пусть m = 18,  n = 12

Выполним разложение на простые множители.

Множители числа m: 2 3 3

Множители числа n: 2 2 3

Выделим их общие простые множители – это числа 2 и 3. В качестве наибольшего общего делителя нужно взять из произведение: 2 * 3 = 6. НОД(12, 18) = 6.

Пусть m = 36,  n = 48

Множители числа m: 2 2 3 3

Множители числа n: 2 2 2 2 3

Общие простые множители – это числа 2 2 3. Произведение этих множителей равно 12. НОД(36, 48) = 12.

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

Как будем решать задачу

Для хранения множителей числа воспользуемся списком (PascalABC.NET), в него легко добавлять значение командой add.

Описание списка с именем nod в блоке var

var nod:List<integer>;

Создание нового пустого списка в теле программы

nod:=new List<integer>;

Добавление значения в конец списка

nod.add(значение);

Создадим два списка (s1 и s2) для хранения множителей числа m и n соответственно. С помощью конструкции вложенных циклов переберем все элементы списков и сравним на равенство, если множители равны, сохраним их в списке nod, а значения элементов списков сделаем равными -1 и -2 соответственно (чтобы далее их повторное сравнение на равенство было ложным) . В качестве ответа возьмем произведение элементов списка nod командой nod.Product.

Программа на языке программирования Паскаль (разложение чисел на простые множители)

var

  m, n, k1, k2: integer;      

  s1, s2, nod: List<integer>;

begin

  writeln(‘Введите два натуральных числа m и n:’);   

  readln(m, n);  

  s1 := new List<integer>; 

  s2 := new List<integer>; 

  nod := new List<integer>;

  k1 := 2; k2 := 2;  

  while (m > 1) or (n > 1) do   

  begin

    while m mod k1 = 0 do     

    begin

      m := m div k1;      

      s1.Add(k1); //добавить значение в список можно и так: s1+=k1;

    end;     

    k1 += 1;     

    while n mod k2 = 0 do    

    begin

      n := n div k2;       

      s2.Add(k2);     

    end;     

    k2 += 1;   

  end;   

  //writeln(s1, s2); 

  for k1:=0 to s1.Count-1 do //элементы списка нумеруются с 0, длина списка s1.count

    for k2:=0 to s2.Count-1 do

      if s1[k1]=s2[k2] then //s1[k1] – обращение к элементу списка по его номеру

        begin 

        nod.Add(s1[k1]);

        s1[k1]:=-1;

        s2[k2]:=-2;

        end;

  //println(s1,s2,nod);

  println(‘НОД(m,n): ‘,nod.Product);

end.

Это программа состоит из самого большого количества строк. Насколько она эффективна?

Задача на применение НОД

Даны числа: a = 2³ • 3¹⁰ • 5 • 7² , b = 2⁵ • 3 • 11. Чему равен  НОД (a,b)?

Математика и числа

Чётность/нечётность чисел

if Odd (Number) then 
  writeln (Number, ' нечётно')
else
  writeln (Number, ' чётно');

Делимость (кратность) чисел

if Number mod 3 = 0 then
  writeln (Number, ' делится на 3 без остатка');

Наибольший Общий Делитель

{ Евклид (Euclidus) }
function GCD (A: integer;  B: integer): integer;
begin
    while (a <> 0) and (b <> 0) do
       if a >= b then
         a := a mod b
       else 
         b := b mod a;
    GCD := a + b; { один - ноль }
end;

Наименьшее Общее Кратное

function LCM (A: integer;  B: integer): integer; 
begin
     LCM := a * b div GCD (a, b)
end;

Степень

function Power(Base, N: integer): longint;
{ Base - основание , N - степень }
var
   Result: longint;
   i: word;
begin
   Result := 1; { придаём начальное значение }
   for i := 1 to N do
     Result := Result * Base;
 
   Power := Result;
end;

function PowerExp (A, N: real): real;
begin
   if A > 0 then
     PowerExp := Exp ( N * Ln (A) )
   else 
     PowerExp := 0;
end;

Факториал

function Factorial(N: word): longint;
var
   Result: longint;
   i: word;
begin
   Result := 1;
   for i := 1 to N do 
     Result := Result * N;
 
   Power := Result;
end;

function Factorial (N: word): longint;
begin
   if N = 0 then
     Factorial := 1 
   else 
     Factorial := N * Factorial (N - 1);
end;

Вещественный и целый типы

   var
       r : real;
     begin
       r := Round ( 123.456);  {    123 }
       r := Round ( 123.778);  {    124 }
       r := Trunc ( 123.456);  {    123 }
       r := Trunc (-123.778);  {   -123 }
       r := Frac  ( 123.456);  {  0.456 }
       r := Int   ( 123.456);  {  123.0 }
       r := Int   (-123.456);  { -123.0 }
     end.

Случайные числа

  Randomize;
  X := Random (N + 1) - 2 * N;

Как проверить простое ли число?

function isPrime(X: word): boolean;
var
i: integer;
Begin
     isPrime:=false;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     while i <= sqrt(x) do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
 
     isPrime:=true;
End;

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

procedure Factorization(x: word);
var i: word;
 
 procedure DivX; { делим на простое число, пока делится без остатка }
 begin
      while (x>1) and (x mod i = 0) do
      begin
           write(i:4);
           x:= x div i;
      end;
 end;
 
begin
     i:=2;
     DivX;
     i:=3;
     while (i < x div 2) do
     begin
           DivX;
           inc(i,2); { <=> i:=i+2; только нечётные числа }
     end;
     if x>1 then writeln(x:4);
end;

Приближённое представление числа в виде дроби

VAR p,q,qmax:integer;
    d, r, min: real;
BEGIN
   write('r, qmax=');
   readln(r, qmax); { r - не целое число, qmax - кол-во итераций (циклов) }
   p:=0; q:=1; min:=r;
   REPEAT
     IF p / q < r
          THEN inc(p)
          ELSE inc(q);
     d:=abs(r-p/q);
     IF d < min THEN
     BEGIN
          min:=d;
          writeln(p:7,'/',q)
     END
   UNTIL (q >= qmax) OR (d = 0);
   readln;
END.

Как работать с отдельными битами?

FUNCTION IsBitOn (n: word; b : BYTE): BOOLEAN; { Проверяем, установлен ли бит }
BEGIN 
     isBitOn:=((n SHR b) AND 1) = 1
END;
 
PROCEDURE SetBitOn (VAR n: Word; b: BYTE); { Устанавливаем бит }
BEGIN
     N:= N OR (1 SHL b)
END;
 
PROCEDURE XORBit (VAR n: Word; b: BYTE); { Переключаем бит }
BEGIN
     N:= N XOR (1 SHL b)
END;

Как узнать из каких цифр состоит целое число?

Var X : Integer;
Begin
 X:=12345;
 Writeln('Число состоит из таких цифр:');
 While X <> 0 Do
  Begin
   Writeln(X Mod 10);
   X:=X Div 10;
  End;
End.

Как быстро делить/умножать числа на степень двойки ?

i:=i shl 1; { i:=i * 2^1}
i:=i shl 2; { i:=i * 2^2}
{и т.д.}
i:=i shr 1; { i:=i div 2^1}
i:=i shr 2; { i:=i div 2^2}
{и т.д.}

Более быстрое разложение числа на множители

{$N+, E+}
 
function FermaFactorization (N : Comp) : Comp;
 
var
  X, Y, R, Z, ZZ : Comp;
 
begin
 Z := Sqrt(N);
 ZZ := Trunc (Z);
 X := 2 * ZZ + 1;
 Y := 1;
 R := Sqr (ZZ) - N;
 while (R <> 0) do
  begin
   R := R + X;
   X := X + 2;
   repeat
    R := R - Y;
    Y := Y + 2;
   until R <= 0;
  end;
 FermaFactorization := (X - Y) / 2;
end;
 
begin
 Writeln (FermaFactorization(917979909) : 0 : 0);
end.