«1. Обзор

Имея два целых числа, a и b, мы говорим, что они взаимно просты, если единственный множитель, на который они делятся, равен 1. Взаимно простые или взаимно простые числа — это синонимы относительно простых чисел.

В этом кратком руководстве мы рассмотрим решение этой проблемы с помощью Java.

2. Алгоритм наибольшего общего делителя

Оказывается, если наибольший общий делитель (НОД) двух чисел a и b равен 1 (т.е. НОД(a, b) = 1), то a и b относительно основной. В результате определение того, являются ли два числа относительно простыми, состоит просто в том, чтобы выяснить, равен ли НОД 1.

3. Реализация алгоритма Евклида

В этом разделе мы будем использовать алгоритм Евклида для вычисления НОД двух чисел. .

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

Итак, представьте, что у нас есть два целых числа, a и b. В итеративном подходе мы сначала делим a на b и получаем остаток. Затем мы присваиваем a значение b и присваиваем b оставшееся значение. Мы повторяем этот процесс до тех пор, пока b = 0. Наконец, когда мы достигаем этой точки, мы возвращаем значение a как результат НОД, и если a = 1, мы можем сказать, что a и b взаимно просты.

Давайте попробуем это на двух целых числах, a = 81 и b = 35.

В этом случае остаток от 81 и 35 (81 % 35) равен 11. Итак, на первом шаге итерации мы заканчиваем с a = 35 и b = 11. Следовательно, сделаем еще одну итерацию.

Остаток от 35, деленного на 11, равен 2. В результате мы имеем теперь a = 11 (мы поменяли местами значения) и b = 2. Продолжаем.

Еще один шаг приведет к a = 2 и b = 1. Теперь мы приближаемся к концу.

Наконец, после еще одной итерации мы достигнем a = 1 и b = 0. Алгоритм возвращает 1, и мы можем заключить, что 81 и 35 действительно взаимно просты.

3.1. Императивная реализация

Во-первых, давайте реализуем императивную Java-версию алгоритма Евклида, как описано выше: 

int iterativeGCD(int a, int b) {
    int tmp;
    while (b != 0) {
        if (a < b) {
            tmp = a;
            a = b;
            b = tmp;
        }
        tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

Как мы можем заметить, в случае, когда a меньше b, мы меняем значения местами, прежде чем продолжить. Алгоритм останавливается, когда b равно 0.

3.2. Рекурсивная реализация

Теперь давайте рассмотрим рекурсивную реализацию. Это, вероятно, чище, поскольку позволяет избежать явного обмена значениями переменных: 

int recursiveGCD(int a, int b) {
    if (b == 0) {
        return a;
    }
    if (a < b) {
        return recursiveGCD(b, a);
    }
    return recursiveGCD(b, a % b);
}

4. Использование реализации BigInteger

Но подождите — разве алгоритм gcd уже не реализован в Java? Да, это! Класс BigInteger предоставляет метод gcd, реализующий алгоритм Евклида для нахождения наибольшего общего делителя.

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

boolean bigIntegerRelativelyPrime(int a, int b) {
    return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).equals(BigInteger.ONE);
}

5. Заключение

В этом кратком руководстве мы представили решение проблемы нахождения двух чисел относительно простым с использованием трех реализаций алгоритма gcd.

И, как всегда, пример кода доступен на GitHub.