C++ Maximum subset where the sum of each pair of elements is a prime number

Find the largest subset from the given array where the sum of each pair of elements is a prime number. Suppose the maximum element is 100000, for example -

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.

Methods to find the solution

First, to determine if the pair of numbers is prime, we need to check if their sum is odd or even, because except Except for 2, no even number is prime. Moreover, if both numbers are odd or even, their sum may be even.

In this problem, we will take three numbers, x, y and z, any two of them should be odd or even. We will then check if this subset contains pairs of prime numbers and sums, which may be possible if:

• The subset contains some numbers of 1 and some other numbers where NUM 1 should be a prime number.

• Or if the subset contains only two numbers, their sum is a prime number.

Example

 #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 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&#39;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;
}

Output

3
1 1 2

Description of the above code

• First we check the individual number.

• If greater than 0, iterate through the array and check whether each element except 1 is nums[i] 1 is a prime number; if so, print the total number of (ones 1) as a sub The size of the set and all 1's with that number.

• If the given array contains only 1, print all of them because the sum of all pairs will be 2 (prime number).

• If no one is present, check that the sum of each pair in the array is prime.

• Else print -1.

Conclusion

In this tutorial, we discussed a problem where we need to find the largest subset from a given array where the sum of each pair is Prime number. We discussed a way to solve this problem with the help of the Sieve of Eratosthenes and check the number in the array. We also discussed a C program to solve this problem and we can implement it using programming languages ​​like C, Java, Python etc. We hope you found this tutorial helpful.

The above is the detailed content of C++ Maximum subset where the sum of each pair of elements is a prime number. For more information, please follow other related articles on the PHP Chinese website!