C++ 求每对和为素数的最大子集

c++server side programmingprogramming

从给定数组中找出每对和为素数的最大子集。假设最大元素为 100000，例如 −

输入:nums[ ] = { 3, 2, 1,1 }
输出:size = 3, subset = { 2, 1, 1 }
说明:
可以形成子集:{3, 2}、{2, 1} 和 { 2, 1, 1}，
在 {2, 1, 1} 中，对 (2,1) 的和为 3，为素数，
对 (1,1) 的和为 2，也是素数。

输入:nums[ ] = {1, 4, 3, 2}
输出:size = 2, subset = {1, 4}
解释:
可以形成子集:{1, 4}、{4, 3} 和 {3, 2}
所有子集的大小均为 2，因此我们可以取任何子集，例如 1 + 4 =5，这是一个素数。

寻找解决方案的方法

要先确定该对是否为素数，我们需要检查其和是奇数还是偶数，因为偶数不是素数，除了 2。如果两个数字都是奇数或偶数，则两个数字的和可以是偶数。

在这个问题中，我们将取三个数字 x、y 和 z，其中任何两个数字都应该是偶数或奇数。然后我们将检查这个子集是否存在素数和对，如果满足以下条件，那么这可能是可能的:

子集包含一些 1 的数字和一些其他数字，其中 NUM + 1 应该是素数。
或者如果子集仅包含两个和为素数的数字。

示例

 #include <bits/stdc++.h>
using namespace std;
#define M 100001
bool check_prime[M] = { 0 };
int sieve_of_eratosthenes(){
    for (int p = 2; p * p < M; p++){
       // 若未标记则标记
        if (check_prime[p] == 0){
            // 更新 p 的所有倍数
            for (int i = p * 2; i < M; i += p)
              check_prime[i] = 1;
        }
    }
    return 0;
}
int main(){
    sieve_of_eratosthenes();
    int nums[] = {  3, 2, 1, 1};
    int n = sizeof(nums) / sizeof(nums[0]);
        int ones = 0;
    for (int i = 0; i < n; i++)
        if (nums[i] == 1)
            ones++;
    // 如果存在 1 并且
    // 大于 0 的元素也存在
    if (ones > 0){
        for (int i = 0; i < n; i++){
            //检查 num + 1 是否为素数
            if ((nums[i] != 1) and (check_prime[nums[i] + 1] == 0)){
                cout << ones + 1 << endl;
                // 用 nums[i] 打印所有存在的 1
                for (int j = 0; j < ones; j++)
                cout << 1 << &"; &";;
              cout << nums[i] << endl;
                 return 0;
            }
        }
    }
    }
    // 如果子集仅包含 1
    if (ones >= 2){
        cout << ones << endl;
        for (int i = 0; i < those; i++)
            cout << 1 << " ";
        cout << endl;
        return 0;
    }
    // 如果没有 1。
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            // 寻找和为素数的整数对。
            if (check_prime[nums[i] + nums[j]] == 0){
                cout << 2 << endl;
                cout << nums[i] << &" &"; << nums[j] << endl;
                return 0;
              }
        }
    }
// 如果数组中只有一个元素。
    cout << -1 << endl;
    return 0;
}

输出

3
1 1 2

上述代码的解释

首先我们检查数组中 1 的数量。
如果大于 0，则遍历数组并检查除 1 之外的每个元素 nums[i] + 1 是否为素数；如果是，则打印 (ones + 1) 的总数作为子集的大小以及所有具有该数字的 1。
如果给定的数组只包含 1，则打印所有 1，因为所有对的总和将为 2(素数)。
如果没有，则检查数组中的每一对，其和为素数。
否则打印 -1。