从给定数组中找到最大的子集，其中每对元素的和是一个质数。假设最大元素是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 100001bool check_prime[m] = { 0 };int sieve_of_eratosthenes(){ for (int p = 2; p * p < m; p++){ // if it is not marked then mark if (check_prime[p] == 0){ // update all multiples of 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++; // if ones are present and // elements greater than 0 are also present if (ones > 0){ for (int i = 0; i < n; i++){ //checking whether num + 1 is prime or not if ((nums[i] != 1) and (check_prime[nums[i] + 1] == 0)){ cout << ones + 1 << endl; // printing all the ones present with nums[i] for (int j = 0; j < ones; j++) cout << 1 << " "; cout << nums[i] << endl; return 0; } } } // if subsets contains only 1's if (ones >= 2){ cout << ones << endl; for (int i = 0; i < ones; i++) cout << 1 << " "; cout << endl; return 0; } // if no ones are present. for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j++){ // searching for pair of integer having sum prime. if (check_prime[nums[i] + nums[j]] == 0){ cout << 2 << endl; cout << nums[i] << " " << nums[j] << endl; return 0; } } }// if only one element is present in the array. cout << -1 << endl; return 0;}
输出31 1 2
上述代码说明首先我们检查数组中的个数。
如果大于0，则遍历数组，检查除1以外的每个元素是否nums[i] + 1是素数；如果是，则打印 (ones + 1) 的总数作为子集的大小以及具有该数字的所有 1。如果给定数组仅包含 1，打印所有的，因为所有对的总和将为 2（素数）。
如果没有人在场，则检查数组中的每一对的总和为素数。
else print -1。
结论在本教程中，我们讨论了一个问题，其中我们需要从给定数组中找到最大的子集，其中每对的总和为素数。我们讨论了一种借助埃拉托斯特尼筛法来解决这个问题的方法，并检查数组中的个数。我们还讨论了解决此问题的 c++ 程序，我们可以使用 c、java、python 等编程语言来实现。我们希望本教程对您有所帮助。
以上就是c++ 最大子集，其中每对元素的和为质数的详细内容。