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