1. Обзор
Имея два целых числа, a и b , мы говорим, что они взаимно просты, если единственный множитель, на который они делятся, равен 1. Взаимно простые или взаимно простые числа являются синонимами относительно простых чисел.
В этом кратком руководстве мы рассмотрим решение этой проблемы с помощью Java.
2. Алгоритм наибольшего общего фактора
Оказывается, если наибольший общий делитель ( gcd ) двух чисел a и b равен 1 (т.е. gcd(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 .