以每对之和为质数的 C++ 最大子集
从给定的数组中找到最大的子集，其中每对的和是素数。假设最大元素为100000，例如-
Input: nums[ ] = { 3, 2, 1,1 }
Output: size = 3, subset = { 2, 1, 1 }
Explanation:
Subsets can be formed: {3, 2}, {2, 1} and { 2, 1, 1},
In {2, 1, 1} sum of pair (2,1) is 3 which is prime,
and the sum of pairs (1,1) is 2 which is also a prime number.
Input: nums[ ] = {1, 4, 3, 2}
Output: size = 2, subset = {1, 4}
Explanation:
subset can be formed: {1, 4}, {4, 3}, and {3, 2}
All are of size 2 so we can take any subset like 1 + 4 =5 which is a prime number.寻找解决方案的方法
首先要确定这对是否是素数，我们需要检查它的和是奇数还是偶数，因为偶数不是素数，除了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++;
//如果存在并且
//大于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]
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 < ones; i++)
cout << 1 << " ";
cout << endl;
return 0;
}
//如果没有人在场。
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)的总数打印为子集的大小以及所有具有该数字的数。
如果给定的数组只包含一个，则打印所有的对，因为所有对的总和将为2（质数）。
如果不存在，则使用总和素数检查数组中的每一对。
否则打印-1。
结论
在本教程中，我们讨论了一个问题，我们需要从给定的数组中找到最大的子集，其中每对的和是素数。我们讨论了一种在Eratosthenes筛法的帮助下解决这个问题的方法，并检查数组中1的数量。我们还讨论了针对这个问题的C++程序，我们可以使用C、Java、Python等编程语言来解决这个问题。我们希望本教程对您有所帮助。