c++求是否两个数互质

判断两个数是否互质的方法是求它们的最大公约数（GCD）是否为1。以下是C++代码实现：

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

bool isCoPrime(int a, int b) {
    return gcd(a, b) == 1;
}

int main() {
    int a, b;
    cout << "Enter two integers: ";
    cin >> a >> b;
    if (isCoPrime(a, b))
        cout << a << " and " << b << " are co-prime" << endl;
    else
        cout << a << " and " << b << " are not co-prime" << endl;
    return 0;
}

在这个程序中，我们首先定义了一个计算最大公约数的函数`gcd`。然后使用`isCoPrime`函数判断两个数是否互质，如果它们的最大公约数为1，则返回true，否则返回false。最后在main函数中，我们输入两个整数并调用`isCoPrime`函数来判断它们是否互质。

相关问题

请用c++写一个判断两个数是否互质的程序

#include <stdio.h>

// 计算最大公约数
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}

int main() {
int a, b;
printf("请输入两个整数：");
scanf("%d%d", &a, &b);
if (gcd(a, b) == 1) {
printf("%d和%d是互质的\n", a, b);
} else {
printf("%d和%d不是互质的\n", a, b);
}
return 0;
}

C++代码实现，给定n个正整数，将它们分组，使得每组中任意两个数互质。输入：第一行是一个正整数n。1 ≤ n ≤ 10。 第二行是n个不大于10000的正整数。输出：一个正整数，即最少需要的组数。

这个问题可以通过欧几里得算法来解决，寻找两数的最大公约数，如果最大公约数为1，则这两个数互质。我们可以使用哈希表（unordered_set）存储每个数字及其已知互质的数字集合，然后遍历整个数组，尝试把当前元素添加到每个已知互质集合中，检查是否可以形成互质的组合。若无法形成，则创建一个新的互质集合。最后返回互质集合的数量作为结果。

下面是一个简单的C++代码实现：

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

unordered_set<int> gcdSet(int n) {
    unordered_set<int> groups;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        bool added = true;
        for (auto &group : groups) {
            int gcd = __gcd(nums[i], group);
            if (gcd != 1) {
                added = false;
                break;
            }
        }
        if (added) {
            groups.insert(nums[i]);
        } else {
            groups.insert({nums[i]});
        }
    }
    return groups;
}

int main() {
    int n;
    cin >> n;
    int result = 0;
    for (const auto &group : gcdSet(n)) {
        result++;
    }
    cout << result << endl;
    return 0;
}