SBP-Program

получайте знания здесь

f

tw

in

Алгоритм Евклида для НОД

Нахождение наибольшего общего делителя двух целых чисел.

Пусть даны целые числа:

A и B
A > B

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

1. Если разделить A на B, получим частное k0 и, возможно, остаток r1:

A : B = k0
остаток r1

Это можно записать так:

A = B * k0 + r1

2. Далее, если разделить B на остаток r1, получим частное k1 и, возможно, остаток r2:

B : r1 = r1 * k1
остаток r2

Это можно записать так:

B = r1 * k1 + r2

3. Далее, если разделить r1 на остаток r2, получим частное k2 и, возможно, остаток r3:

r1 : r2 = r2 * k2
остаток r3

Это можно записать так:

r1 = r2 * k2 + r3

4. Продолжая таким образом, в какой-то момент получим остаток, равный нулю:

rk - 1 : rk = rk * kk
остаток 0

Это можно записать так:

rk - 1 = rk * kk + 0

Число rk и будет наибольшим общим делителем целых чисел A и B

НОД(A, B) = rk

Запишем алгоритм Евклида кратко:

1. A = B * k0 + r1
2. B = r1 * k1 + r2
3. r1 = r2 * k2 + r3
...
k. rk - 1 = rk * kk + 0

Когда получаем ноль в остатке, поиск наибольшего общего делителя прекращаем ибо НОД уже найден и им является число rk.

Ответ:

НОД(A, B) = rk