Калькулятор алгоритма Евклида

Логика вычислений

Калькулятор находит наибольший общий делитель (НОД) двух целых неотрицательных чисел методом алгоритма Евклида — через последовательные деления с остатком. На каждом шаге большее число делится на меньшее, и дальше работа идёт с парой «делитель — остаток», пока остаток не станет нулём.

Сначала из двух исходных чисел выбираются большее и меньшее:

a₀ = max(n₁, n₂)    b₀ = min(n₁, n₂)

где:

• n₁, n₂ — введённые целые неотрицательные числа;
• a₀, b₀ — начальные значения делимого и делителя для первого шага.

Для каждого шага k = 0, 1, 2, … вычисляется неполное частное и остаток:

q_k = ⌊a_k / b_k⌋    r_k = a_k − q_k × b_k

где:

• a_k, b_k — делимое и делитель на шаге k;
• q_k — неполное частное (целая часть деления);
• r_k — остаток от деления, 0 ≤ r_k < b_k.

Перед следующим шагом делитель становится новым делимым, а остаток — новым делителем:

a_{k+1} = b_k    b_{k+1} = r_k

Процесс повторяется до тех пор, пока очередной остаток не обратится в ноль. Последний ненулевой делитель и есть искомый НОД:

НОД(n₁, n₂) = a_K   при условии  b_K = 0

где:

• K — номер шага, на котором остаток впервые стал равен нулю;
• a_K — значение делимого на этом шаге (равно делителю с предыдущего шага).

Особый случай: одно из чисел равно нулю

Если одно из исходных чисел равно нулю, а второе — положительное, наибольшим общим делителем по определению является ненулевое число (так как любое целое число делит ноль):

НОД(n, 0) = НОД(0, n) = n,  n > 0

Случай, когда оба числа равны нулю, не рассматривается: НОД(0, 0) не определён.