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

Пусть даны два целых числа $x$ и $y$. Не нарушая общности, положим, что $x > 0$ и $y > 0$, в противном случае заменяем отрицательное число на обратное.

Число $k$ называют общим делителем, если $k \mid x$ (говорят $k$ делит $x$) и $k \mid y$. Тогда $\exists ! g$ - общий делитель такой, что $\forall k$ $k \mid g$, такой общий делитель $g$ называют наибольшим общим делителем, и обозначают $g = НОД(x, y)$.

Алгоритм Евклида для целых чисел

Можно предположить, что $x > y$, в противном случае просто поменяем $x$ и $y$. Тогда $x$ можно поделить с остатком на $y$:

$q_0$ называют неполным частным, а $r_1$ - остатком от деления, причём $0 \leq r_1 < y$. Далее поделим с остатком $y$ на $r_1$:

продолжая так далее на некотором шаге $n$ остаток $r_n$ окажется равным нулю, таким образом получаем последовательность:

Тогда $НОД(x, y)$ - наибольший общий делитель $x$ и $y$ будет равен $r_{n-1}$.

Формально алгоритм будет иметь вид:

Корректность

Пусть $x = y\cdot q + r$, тогда $НОД(x, y) = НОД(y, r)$.

$НОД(r, 0) = r$, $\forall r > 0$

Реализация

Рекурсивная

int GCD(const int x, const int y) {
    if (y == 0)
        return x;
    return GCD(y, x%y);
}

Нерекурсивная

int GCD(const int x, const int y) {
    int r1(x), r2(y);
    while (r2 > 0) {
        r1 %= r2;
        swap(r1, r2);
    }
    return r1;
}

НОК

Число $m$ называют общим кратным, если $x\mid m$ и $y\mid m$.

Тогда $\exists ! n$ - общее кратное такое, что $\forall m$ $n \mid m$, такое общее кратное $n$ называют наименьшим общим кратным, и обозначают $n = НОК(x, y)$.

Вычисление наименьшего общего кратного сводится к вычислению наибольшего общего делителя:

Реализация

int LCM(const int x, const int y) {
    return x/GCD(x, y)*y;
}

Практика

• НОД:
  • mccme 111234
  • mccme 147
• НОК:
  • mccme 146
  • mccme 1422

tutorials arithmetic
easy arithmetic