C++ 最大子集，其中每对元素的和为质数

1. 题目描述

在 C++ 中，给定一个整数数组，你需要找到该数组中最大的子集，其中每对元素的和是一个质数。并返回该子集的元素个数。如果有多个解决方案，返回长度最长的子集。

示例 1:

输入: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

输出: 6
解释: 最大的子集为 [2,3,5,7,11,13]。

2. 题目分析

该题要求的是最大的子集中，每对元素的和都是质数。因此，我们需要从原始的数组中找到和是质数的数对，并找到最大的子集。

首先，我们可以通过暴力枚举的方式来找到和是质数的数对。具体来说，我们可以使用双重循环来找到能组成质数的数对，并将这些数对存储在一个数组或者容器中。具体代码实现如下：

// 判断一个数是否是质数

bool isPrime(int n) {
    if (n < 2) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}
vector> getPrimeSumPairs(vector &nums) {
    vector> result;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            int sum = nums[i] + nums[j];
            if (isPrime(sum)) {
                result.push_back(make_pair(i, j));
            }
        }
    }
    return result;
}

上述代码中，我们定义了一个 isPrime 函数来判断一个数是否是质数。然后，我们定义了一个 getPrimeSumPairs 函数来获取原始数组中所有能够组成质数的数对，该函数返回一个 pair 的数组，其中每个 pair 中的两个元素分别表示原始数组中的下标。

接下来，我们可以使用动态规划来求解最大子集。具体来说，我们定义一个数组 dp，其中 dp[i] 表示原始数组中以第 i 个元素为结尾的最大子集的长度。初始时，我们将 dp 数组元素都设置为 1，表示每个元素本身都是一个子集。然后，我们在遍历过程中不断更新 dp 数组，直到得到最终的结果为止。具体代码实现如下：

int maxPrimeSubset(vector &nums) {

    vector> primeSumPairs = getPrimeSumPairs(nums);
    vector dp(nums.size(), 1);
    int result = 1;
    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            // 判断 nums[j] 和 nums[i] 是否存在一个能组成质数的数对
            auto iter = find_if(primeSumPairs.begin(), primeSumPairs.end(), [&](pair &p) {
                return p.first == j && p.second == i;
            });
            if (iter == primeSumPairs.end()) {
                continue;
            }
            dp[i] = max(dp[i], dp[j] + 1);
            result = max(result, dp[i]);
        }
    }
    return result;
}

上述代码中，我们使用了 STL 中的 find_if 函数来找到能够组成质数的数对。然后，我们使用 dp 数组来不断更新最大子集所包含的元素个数，最终返回最大子集的长度即可。

3. 总结

本文分析了 C++ 中求解最大子集，其中每对元素的和为质数的题目。我们首先使用暴力枚举的方式来找到能够组成质数的数对，然后使用动态规划来求解最大子集。通过本文的分析，我们可以学习到如何使用动态规划求解最大子集问题，并学习到了如何在 C++ 中实现这个算法。