C++ 算法：求一组数中两两互质的最大子集

要找出一组数中最多能选出多少个数，使这些数两两互质，可以使用贪心算法。\n\n首先，将所有数按照从大到小的顺序排序。\n\n然后，从第一个数开始依次判断是否与已选出的数两两互质。如果是互质的，则将该数加入已选出的数的集合中。\n\n最后，返回已选出的数的数量。\n\n以下是使用 C++ 实现的代码：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <algorithm>\n\nbool isCoprime(int a, int b) { // 判断两个数是否互质\n while (b != 0) {\n int temp = a;\n a = b;\n b = temp % b;\n }\n return a == 1;\n}\n\nint maxCoprimeCount(std::vector<int>& nums) {\n std::sort(nums.begin(), nums.end(), std::greater<int>()); // 按照从大到小的顺序排序\n std::vector<int> selected;\n\n for (int i = 0; i < nums.size(); i++) {\n bool isCoprimeWithSelected = true;\n for (int j = 0; j < selected.size(); j++) {\n if (!isCoprime(nums[i], selected[j])) {\n isCoprimeWithSelected = false;\n break;\n }\n }\n if (isCoprimeWithSelected) {\n selected.push_back(nums[i]);\n }\n }\n\n return selected.size();\n}\n\nint main() {\n std::vector<int> nums = { 2, 3, 4, 5, 6, 7, 8, 9, 10 };\n int maxCount = maxCoprimeCount(nums);\n std::cout << "最多能选出的数的数量为：" << maxCount << std::endl;\n return 0;\n}\n\n\n在上述代码中，我们先将给定的一组数按照从大到小的顺序排序，然后使用两层循环来判断每个数与已选出的数是否互质。如果是互质的，则将该数加入已选出的数的集合中。最后返回已选出的数的数量。\n\n对于给定的一组数 { 2, 3, 4, 5, 6, 7, 8, 9, 10 }，运行上述代码，输出为最多能选出的数的数量为 5，即选出的数为 { 2, 3, 5, 7, 9 }。