Напишите логическую функцию, которая определяет, являются ли два переданные ей числа...

Question

Напишите логическую функцию, которая определяет, являются ли два переданные ей числа взаимно простыми, то есть, не имеющими общих делителей, кроме 1.
Программа должна быть написана с помощью функций.(на c++)

Answer 1

Ищем НОД по алгоритму Евклида и возвращаем результат сравнения НОДа с единицей.

#include
 
int gcd(int a, int b) {
    if (a * b == 0) 
        return a + b;
    return gcd(b, a % b);
}
 
bool is_coprime(int a, int b) {
    return gcd(a, b) == 1; 
}
 
int main() {
    int a, b;
    std::cin >> a >> b;
    std::cout << (is_coprime(a, b)? "coprime" : "not coprime");<br>    return 0;
}