Как найти nod евклид

Наибольший общий делитель (НОД) чисел a и b — это наибольшее число, на которое делятся без остатка числа a и b.

Среди всех способов нахождения наибольшего общего делителя для двух чисел алгоритм Евклида наиболее удобный и простой.

Нахождения НОД и НОК по алгоритму Евклида методом деления

Как известно, деление с остатком целых чисел a — делимое и b — делитель, где b ≠ 0, подразумевает нахождение таких целых чисел q и r, что выполняется равенство:
a = b ∙ q + r, где
q — называется неполным частным,
r — остаток от деления, который не может быть отрицательным числом и по модулю не может быть больше делителя.

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

Пример 1

Найдем НОД (36; 30), для этого сначала найдем остаток от деления 36 на 30
36 : 30 = 1 (остаток 6), так как 36 = 30 ∙ 1 + 6, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 30 на 6
30 : 6 = 5 (остаток 0) так как 30 = 6 ∙ 5 + 0, остаток от деления равен нулю, значит НОД равен предыдущему остатку от деление 6
Ответ: НОД (36; 30) = 6
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (36; 30) = (36 ∙ 30) : 6 = 180

Пример 2

Найдем НОД (176; 36), для этого сначала найдем остаток от деления 176 на 36
176 : 36 = 4 (остаток 32) так как 176 = 36 ∙ 4 + 32, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 36 на 32
36 : 32 = 1 (остаток 4) так как 36 = 32 ∙ 1 + 4, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 32 на 4
32 : 4 = 8 (остаток 0) так как 32 = 4 ∙ 8 + 0, остаток от деления равен нулю, значит НОД равен предыдущему остатку от деление 4
Ответ: НОД (176; 36) = 4
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (176; 36) = (176 ∙ 36) : 4 = 1584

Нахождения НОД и НОК по алгоритму Евклида методом вычитания

Суть метода вычитания состоит в том, что необходимо из большего числа вычитать меньшее, если результат вычитания не равен нулю,
тогда уменьшаемое заменяем на получившуюся разность, если разность равна нулю, то НОД равен предыдущему значению разности.

Приведем примеры:

Пример 1

Найдем НОД (36; 30)
36 — 30 = 6
30 — 6 = 24
24 — 6 = 18
18 — 6 = 12
12 — 6 = 6
6 — 6 = 0
Ответ: НОД (36; 30) = 6
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (36; 30) = (36 ∙ 30) : 6 = 180

Пример 2

Найдем НОД (176; 36)
176 — 36 = 140
140 — 36 = 104
104 — 36 = 68
68 — 36 = 32
36 — 32 = 4
32 — 4 = 28
28 — 4 = 24
24 — 4 = 20
20 — 4 = 16
16 — 4 = 12
12 — 4 = 8
8 — 4 = 4
4 — 4 = 0
Ответ: НОД (176; 36) = 4
Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b)
НОК (176; 36) = (176 ∙ 36) : 4 = 1584

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

Для начала разберемся, что это и как это работает. Алгоритм Евклида позволяет найти нам наибольший общий делитель чисел. Как это работает:
Пусть a = 18, b = 30.
Цикл: a!=0 and b!=0
Если a > b, то a = a % b, если меньше, то b = b % a, таким образом мы сначала находим остаток деления, а потом повторяем действия. У нас a < b, значит, ищем остаток деления b % a (30 % 18) = 12, присваиваем b = 12, повторяем цикл но теперь у нас уже a > b(b = 12)
значит выполняем a % b (18 % 12) = 6? снова переходим к циклу, теперь снова b > a, значит выполняем b % a (30 % 6), остаток от деления 0, на этом мы прекращаем наш цикл и узнаем, что наибольший общий делитель 18 и 30 = 6. и выводим a + b (b = 0, a = 6).

Python

#!/usr/bin/env python
a = 18
b = 30
 
while a!=0 and b!=0:
    if a > b:
        a = a % b
    else:
        b = b % a
 
print (a+b)

Perl:

 sub nod
 {
 return  $_[0] != 0  ?  nod ( ( $_[1] % $_[0] ), $_[0] )  :  $_[1];
 }

C:

 int gcd(int a, int b) {
   int c;
   while (b) {
      c = a % b;
      a = b;
      b = c;        
   }
   return abs(a);
 }

Pascal:

  function nod( a, b: longint): longint; 
  begin
   while (a <> 0) and (b <> 0) do
     if a >= b then 
       a:= a mod b 
     else 
       b:= b mod a;
   nod:= a + b;
  end;

Java:

public class GCD {
    public static int gcd(int a,int b) {
        while (b !=0) {
            int tmp = a%b;
            a = b;
            b = tmp;
        }
        return a;
    }
}

C#:

int gcd(int a, int b)
{
    while (b != 0)
        b = a % (a = b);
    return a;
}