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

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

Число называют общим делителем, если (говорят делит ) и . Тогда - общий делитель такой, что , такой общий делитель называют наибольшим общим делителем, и обозначают .

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

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

называют неполным частным, а - остатком от деления, причём . Далее поделим с остатком на :

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

Тогда - наибольший общий делитель и будет равен .

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

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

Пусть , тогда .

,

Реализация

Рекурсивная

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;
}

НОК

Число называют общим кратным, если и .

Тогда - общее кратное такое, что , такое общее кратное называют наименьшим общим кратным, и обозначают .

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

Реализация

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

Практика

tutorials arithmetic