Автор оригинала: Antonio Manuel Moreno Delgado.
1. Обзор
Учитывая два целых числа, a и b , мы говорим, что они относительно простые, если единственный фактор, который делит оба, равен 1. Взаимно простые или взаимно простые числа являются синонимами для относительно простых чисел.
В этом кратком руководстве мы рассмотрим решение этой проблемы с помощью Java.
2. Алгоритм Наибольшего общего коэффициента
Как оказалось, если наибольший общий делитель ( gcd ) из 2 чисел a и b равен 1 (т. е. gcd(a, ), то a и b относительно просты. В результате определение того, являются ли два числа относительно простыми, состоит просто в том, чтобы найти, является ли gcd 1.
3. Реализация Евклидова алгоритма
В этом разделе мы будем использовать евклидов алгоритм для вычисления gcd из 2 чисел.
Прежде чем мы покажем нашу реализацию, давайте обобщим алгоритм и рассмотрим краткий пример того, как его применять для понимания.
Итак, представьте, что у нас есть два целых числа, a и b . В итеративном подходе мы сначала делим a на b и получаем остаток. Затем мы назначаем a значение b , и мы назначаем b оставшееся значение. Мы повторяем этот процесс до тех пор, пока b = 0 . Наконец, когда мы достигнем этой точки, мы вернем значение a в качестве результата gcd , и если a = 1 , мы можем сказать, что a и b относительно просты.
Давайте попробуем это на двух целых числах, a и b .
В этом случае оставшаяся часть 81 и 35 (81 % 35) это 11 . Итак, на первом шаге итерации мы заканчиваем a и b . Следовательно, мы сделаем еще одну итерацию.
Оставшаяся часть 35 делится на 11 это 2 . В результате теперь у нас есть a (мы поменялись значениями) и b . Давай продолжим.
Еще один шаг приведет к a и b . Теперь мы приближаемся к концу.
Наконец, после еще одной итерации мы достигнем a и b . Алгоритм возвращает 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 .