Question

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

Answer 1

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

#include <iostream>
 
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");
    return 0;
}