Как найти наибольший общий делитель алгоритм евклида

Алгоритм Евклида — нахождение наибольшего общего делителя

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Решение задачи на языке программирования Python

Алгоритм нахождения НОД делением

  1. Большее число делим на меньшее.
  2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
  3. Если есть остаток, то большее число заменяем на остаток от деления.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6

a = int(input())
b = int(input())
 
while a != 0 and b != 0:
    if a > b:
        a = a % b
    else:
        b = b % a
 
print(a + b)

В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для определения НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.

Если условием завершения цикла является равенство хотя бы одной из переменных нулю (a == 0 or b == 0), то условием продолжения его работы является обратное этому условие — обе переменные должны иметь отличные от нуля значения (a != 0 and b != 0).

Блок-схема алгоритма Евклида

Для того, чтобы вышеприведенная программа могла обрабатывать отрицательные числа, в логическом выражении при if должны сравниваться модули значений переменных: if abs(a) > abs(b):. Иначе большим числом может оказаться меньшее по модулю. В этом случае интерпретатор Питона в качестве остатка от деления выдает вещественное число. В результате это приводит к зацикливанию, так как низвести переменные до нуля становится как минимум маловероятным.

Алгоритм нахождения НОД вычитанием

  1. Из большего числа вычитаем меньшее.
  2. Если получается 0, значит, числа равны друг другу и являются НОД (следует выйти из цикла).
  3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 — 18 = 12
18 — 12 = 6
12 — 6 = 6
6 — 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6

a = int(input())
b = int(input())
 
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
 
print(a)

Функция, вычисляющая НОД

def gcd(m, n):
    while m != n:
        if m > n:
            m = m - n
        else:
            n = n - m
    return n
 
 
a = int(input())
b = int(input())
 
print(gcd(a, b))

Функция gcd модуля math

В модуле math языка программирования Python есть функция gcd, вычисляющая наибольший общий делитель двух чисел.

>>> import math
>>> math.gcd(30, 18)
6

Больше задач в PDF

Источник

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

Для начала разберемся, что это и как это работает. Алгоритм Евклида позволяет найти нам наибольший общий делитель чисел. Как это работает:
Пусть 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;
}
Источник

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

Содержание:

  • Что такое алгоритм Евклида
  • Понятие НОД
  • Основная суть алгоритма Евклида

    • Последовательность нахождения НОД при помощи деления:
    • Последовательность нахождения НОД при помощи вычитания:
  • Примеры решения задач с алгоритмом Евклида

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

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

Алгоритм Евклида — это алгоритм, основная функция которого заключается в поиске наибольшего общего делителя (НОД) для двух целых чисел.

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

Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.

Понятие НОД

Аббревиатура НОД расшифровывается как «наибольший общий делитель».

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

Основная суть алгоритма Евклида

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

a, b, x1, x2, x3, … xn.

В нем каждое последующее число — это остаток от деления двух предыдущих, ряд заканчивается, когда остаток от деления становится равным 0 — при условии использования деления.

В нем каждое последующее число является результатом вычитания двух предыдущих, ряд заканчивается, когда частное становится равным 0 — при условии использования вычитания.

Последовательность нахождения НОД при помощи деления:

  1. Большее число делится на меньшее.
  2. Если результат деления:
  • без остатка, то меньшее число и есть НОД;
  • с остатком, тогда большее число заменяется на остаток.
  1. Переход к пункту 1.

Пример №1

60 / 36 = 1 (остаток 24)

36 / 24 = 1 (остаток 12)

24 / 12 = 2 (остаток 0)

НОД для 60 и 36 равен 12 (делитель).

Последовательность нахождения НОД при помощи вычитания:

  1. Из большего числа вычитается меньшее.
  2. Если результат вычитания:
  • равен 0, то числа равны друг другу и являются НОД;
  • не равен 0, в таком случае большее число заменяется на результат вычитания.
  1. Переход к пункту 1.

Пример №2

60 — 36 = 24

36 — 24 = 12

24 — 12 = 12

12 — 12 = 0

НОД для 60 и 36 равен 12 (уменьшаемое, вычитаемое)

Примеры решения задач с алгоритмом Евклида

Задача №1

Найти наибольший общий делитель для чисел 128 и 96.

Решение:

128 — 96 = 32

96 — 32 = 64

64 — 32 = 32

32 — 32 = 0

Или

128 / 96 = 1 (остаток 32)

96 / 32 = 3

Ответ: 32

Задача №2

Найти наибольший общий делитель для чисел 37 и 17.

Решение:

37 / 17 = 2 (остаток 3)

17 / 3 = 5 (остаток 2)

3 / 2 = 1 (остаток 1)

2 / 1 = 2 (остаток 0)

Или

37 — 17= 20

20 — 17 = 3

17 — 3 = 14

14 — 3 = 11

11 — 3 = 8

8 — 3 = 5

5 — 3 = 2

3 — 2 = 1

2 — 1 = 1

1 — 1 = 0

Числа 37 и 17 являются простыми, соответственно, их НОД — единица. Совет: перед вычислениями проверяйте таблицу простых чисел.

Ответ: 1

Насколько полезной была для вас статья?

Рейтинг: 4.50 (Голосов: 18)

Выделите текст и нажмите одновременно клавиши «Ctrl» и «Enter»

Текст с ошибкой:

Расскажите, что не так

Поиск по содержимому

Источник

Как вы помните, наибольший общий делитель (НОД) для двух целых чисел A и B — это наибольшее натуральное число, на которое делятся и A, и B

Алгоритм Евклида — это метод быстрого нахождения НОД для двух целых чисел.

Алгоритм

Алгоритм Евклида для нахождения НОД(A, B) выглядит следующим образом:

  • Если A = 0, тогда НОД(A, B) = B, поскольку НОД(0, B) = B, и алгоритм останавливается.
  • Если B = 0, тогда НОД(A, B) = A, поскольку GCD(A, 0) = A, и алгоритм останавливается.
  • Делим A на B с остатком (A = B⋅Q + R)
  • Находим НОД(B, R) при помощи алгоритма Евклида, поскольку НОД(A ,B) = НОД(B, R)

Пример:

  • A=270, B=192
  • A ≠0
  • B ≠0
  • Делим столбиком A на B, получается 270/192 = 1 с остатком 78. Можем записать результат в виде: 270 = 192 * 1 +78
  • Ищем НОД(192, 78), поскольку НОД(270, 192) = НОД(192, 78)
  • A ≠0
  • B ≠0
  • Делим столбиком A на B, получается 192/78 = 2 с остатком 36. Можем записать результат в виде:
  • 192 = 78 * 2 + 36
  • Ищем НОД(78, 36), поскольку НОД(192, 78) = НОД(78, 36)
  • A ≠0
  • B ≠0
  • Делим столбиком A на B, получается 78/36 = 2 с остатком 0. Можем записать результат в виде:
  • 78 = 36 * 2 + 6
  • Ищем НОД(36,6), поскольку НОД(78,36) = НОД(36,6)
  • A ≠0
  • B ≠0
  • Делим столбиком A на B, получается 36/6 = 6 с остатком 0. Можем записать результат в виде:
  • 36 = 6 * 6 + 0
  • Ищем НОД(6,0), поскольку НОД(36,6) = НОД(6,0)
  • A ≠0
  • B =0, НОД(6,0)=6

НОД(270,192) = НОД(192,78) = НОД(78,36) = НОД(36,6) = НОД(6,0) = 6

Принцип работы алгоритма Евклида

Алгоритм Евклида основан на следующих свойствах:

  • НОД(A,0) = A
  • НОД(0,B) = B
  • Если A = B⋅Q + R и B≠0, то НОД(A, B) = НОД(B, R), где Q — целое число, а R — целое число от 0 до B-1

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

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

Мы можем понять принцип действия алгоритма, доказав эти три свойства.

Мы можем доказать, что НОД(A, 0) = A, следующим образом:

  • Наибольшее число, на которое A делится без остатка, — это A.
  • Число 0 делится на все целые числа, поскольку для любого целого C верно выражение C ⋅ 0 = 0. Следовательно, 0 делится на A без остатка.
  • Следовательно, наибольший общий делитель чисел A и 0 — это A.

Аналогично доказывается, что НОД(0, B)=B (принцип доказательтва тот же, только A заменяем на B).

Чтобы доказать, что НОД(A, B) = НОД(B, R), мы должны сначала доказать, что НОД(A, B) = НОД(B, A-B).

Возьмём три целых числа A, B и C, такие что A-B = C.

Доказательство того, что НОД(A, B) является делителем числа C

По определению, A делится на НОД(A, B) без остатка. Следовательно, A кратно НОД(A, B), то есть существует такое целое X, что X⋅НОД(A, B)=A.

По определению, B делится на НОД(A, B) без остатка. Следовательно, B кратно НОД(A, B), то есть существует такое целое Y, что Y⋅НОД(A, B)=B.

  • X⋅НОД(A,B) — Y⋅НОД(A,B) = C
  • (X — Y)⋅НОД(A,B) = C

То есть, как видим, НОД(А, B) является делителем числа C.

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

Доказательство того, что НОД(B, C) является делителем числа A

По определению, B делится на НОД(B, C) без остатка. Следовательно, B кратно НОД(B, C), то есть существует такое целое M, что M⋅НОД(B, C)=B.

По определению, C делится на НОД(B, C) без остатка. Следовательно, C кратно НОД(B, C), то есть существует такое целое N, что N⋅НОД(B, C)=N.

  • B+C=A
  • M⋅НОД(B, C) + N⋅НОД(B, C) = A
  • (M + N)⋅НОД(B, C) = A

То есть, как видим, НОД(B, C) является делителем числа A.

Данное доказательство можно проиллюстрировать следующей схемой

Доказательство того, что НОД(A, B) = НОД(A, A-B)

  • По определению, число B делится на НОД(A, B) без остатка.
  • Мы доказали, что НОД(A, B) является делителем C.
  • Поскольку НОД(A, B) является делителем и числа B, и числа C, значит, это общий делитель чисел B и C.

НОД(A, B) должен быть меньше или равен НОД(B, C), поскольку НОД(B, C) — «наибольший» общий делитель чисел B и C.

  • По определению, число B делится на НОД(B, C) без остатка.
  • Мы доказали, что НОД(B, C) является делителем A.
  • Поскольку НОД(B, C) является делителем и числа A, и числа B, значит, это общий делитель чисел A и B .

НОД(B, C) должен быть меньше или равен НОД(A, B), поскольку НОД(A, B) — «наибольший» общий делитель чисел A и B.

Значит, раз НОД(A, B) ≤ НОД(B, C) и НОД(B, C) ≤ НОД(A, B), тогда мы можем сделать вывод:

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

Доказательство того, что НОД(A, B) = НОД(B, R)

Мы доказали, что НОД(A, B) = НОД(B, A-B)

Порядок чисел не имеет значения, то есть, мы можем сказать, что НОД(A, B) = НОД(A-B, B)

Мы можем многократно применить свойство НОД(A, B) = НОД(A-B, B), тогда получится:

НОД(A, B)=НОД(A-B, B)=НОД(A-2B, B)=НОД(A-3B, B)=…=НОД(A-Q⋅B, B)

Однако A= B⋅Q + R, поэтому A-Q⋅B=R

Из этого следует, что НОД(A, B)=НОД(R, B)

Порядок чисел не имеет значения, следовательно:

Источник

Понравилась статья? Поделить с друзьями:
  • Интернет мтс без доступа к интернету как исправить
  • Памятка как составить план сочинения
  • Если неправильно указан стаж в сзв стаж как исправить
  • Как найти что нибудь на странице
  • Электронная трудовая книжка как найти свои данные