Largest subset with sum of every pair as prime

0 0 10 minutes read

Given an array A[], find a subset of maximum size in which sum of every pair of elements is a prime number. Print its length and the subset. Consider many queries for different arrays and maximum value of an element as 100000.

Examples :

Input : A[] = {2, 1, 2}
Output : 2
         1 2
Explanation :
Here, we can only form subsets with size 1 and 2.
maximum sized subset = {1, 2}, 1 + 2 = 3, which 
is prime number.
So, Answer = 2 (size), {1, 2} (subset)

Input : A[] = {2, 1, 1}
Output : 3
         1 1 2
Explanation :
Maximum subset = {2, 1, 2}, since 1 + 2 = 3,
1 + 1 = 2, both are prime numbers.
Answer = 3 (size), {2, 1, 1} (subset).

Let’s make some observations and then move to problem. Sum of two numbers is even if and only both the numbers are either odd or even. An even number cannot be a prime number except 2. Now, if we take three numbers a, b and c, two of them should be either odd or even(Pigeonhole theorem). So, our solution exists only in two cases – (Let the subset be B)

Case I : When B contains only two integers(>1) whose sum is a prime number.
Case II : When B contains some number of ones(1s) and another number X, where X + 1 should be a prime(Only possible when X is an even number).

First count the number of ones in the array using a for loop.

If the count of 1s is greater than 0, then traverse the whole the array and check if [A[i] + 1] is a prime number and (A[i] != 1), if found any, print the size of subarray as (count of 1s) +1 and all the ones(1s) and the found A[i]. Exit the program.
If the above step fails (i.e, A[i] not found), print all the ones(1s). Exit the program.
If above step fails (i.e, count of 1s = 0), Check every pair of elements in the array for their sum to be a prime. Print 2 and the pair of integers.
Else Print -1.

Below is implementation of above approach :

C++

// CPP program to find a subset in which sum of 
// every pair in it is a prime
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 100001
 
bool isPrime[MAX] = { 0 };
 
int sieve()
{
    for (int p = 2; p * p < MAX; p++) 
    {
        // If isPrime[p] is not changed, then it
        // is a prime
        if (isPrime[p] == 0) 
        {
            // Update all multiples of p
            for (int i = p * 2; i < MAX; i += p)
                isPrime[i] = 1;
        }
    }
}
 
int findSubset(int a[], int n)
{
    int cnt1 = 0;
 
    // Counting no.of ones in the array
    for (int i = 0; i < n; i++) 
        if (a[i] == 1)
            cnt1++;
 
    // Case-I: count of ones(1s) > 0 and 
    // an integer > 1 is present in the array
    if (cnt1 > 0) 
    {
        for (int i = 0; i < n; i++) 
        {
            // Find a[i], where a[i] + 1 is prime.
            if ((a[i] != 1) and (isPrime[a[i] + 1] == 0)) 
            {
                cout << cnt1 + 1 << endl;
 
                // Print all the ones(1s).
                for (int j = 0; j < cnt1; j++) 
         
                cout << 1 << " ";
                cout << a[i] << endl; // print a[i].
                return 0;
            }
        }
    }
 
    // Case-II: array contains only ones(1s)
    if (cnt1 >= 2) 
    {
        cout << cnt1 << endl;
 
        // Print all ones(1s).
        for (int i = 0; i < cnt1; i++) 
            cout << 1 << " ";
 
        cout << endl;
        return 0;
    }
 
    // Case-III: array does not contain 1s
    for (int i = 0; i < n; i++) 
    {
        for (int j = i + 1; j < n; j++) 
        {
            // Find a pair of integers whose sum is prime
            if (isPrime[a[i] + a[j]] == 0) 
            {
                cout << 2 << endl;
                cout << a[i] << " " << a[j] << endl;
                return 0;
            }
        }
    }
 
    // Array contains only a single element.
    cout << -1 << endl;
}
 
// Driver function
int main()
{
    sieve();
    int A[] = { 2, 1, 1 };
    int n = sizeof(A) / sizeof(A[0]);
    findSubset(A, n);
    return 0;
}

Java

// Java program to find a 
// subset in which sum of 
// every pair in it is a prime
import java.io.*;
 
class GFG
{
    static int MAX = 100001;
     
    static int []isPrime = new int[MAX];
     
    static int sieve()
    {
        for (int p = 2; 
                 p * p < MAX; p++) 
        {
            // If isPrime[p] is 
            // not changed, then
            // it is a prime
            if (isPrime[p] == 0) 
            {
                // Update all
                // multiples of p
                for (int i = p * 2; 
                         i < MAX; i += p)
                    isPrime[i] = 1;
            }
        }
        return -1;
    }     
    static int findSubset(int []a, int n)
    {
        int cnt1 = 0;
     
        // Counting no. of 
        // ones in the array
        for (int i = 0; i < n; i++) 
            if (a[i] == 1)
                cnt1++;
     
        // Case-I: count of 
        // ones(1s) > 0 and 
        // an integer > 1 is 
        // present in the array
        if (cnt1 > 0) 
        {
            for (int i = 0; i < n; i++) 
            {
                // Find a[i], where
                // a[i] + 1 is prime.
                if ((a[i] != 1) && 
                    (isPrime[a[i] + 1] == 0)) 
                {
                    System.out.println(cnt1 + 1);
     
                    // Print all 
                    // the ones(1s).
                    for (int j = 0;
                             j < cnt1; j++) 
             
                    System.out.print(1 + " ");
                    System.out.println(a[i]); // print a[i].
                    return 0;
                }
            }
        }
     
        // Case-II: array contains
        // only ones(1s)
        if (cnt1 >= 2) 
        {
            System.out.println(cnt1);
     
            // Print all ones(1s).
            for (int i = 0; 
                     i < cnt1; i++) 
                System.out.print(1 + " ");
     
            System.out.println();
            return 0;
        }
     
        // Case-III: array does
        // not contain 1s
        for (int i = 0; i < n; i++) 
        {
            for (int j = i + 1; 
                     j < n; j++) 
            {
                // Find a pair of integers
                // whose sum is prime
                if (isPrime[a[i] + a[j]] == 0) 
                {
                    System.out.println(2);
                    System.out.println(a[i] +
                                 " " + a[j]);
                    return 0;
                }
            }
        }
     
        // Array contains only 
        // a single element.
        System.out.println(-1);
        return -1;
    }
     
    // Driver Code
    public static void main(String args[])
    {
        sieve();
        int []A = new int[]{ 2, 1, 1 };
        int n = A.length;
        findSubset(A, n);
    }
}
 
// This code is contributed by 
// Manish Shaw(manishshaw1)

Python3

# Python3 program to find a subset in which 
# sum of every pair in it is a prime
import math as mt
 
MAX = 100001
 
isPrime = [0 for i in range(MAX)]
 
def sieve():
 
    for p in range(2, mt.ceil(mt.sqrt(MAX))): 
         
        # If isPrime[p] is not changed, 
        # then it is a prime
        if (isPrime[p] == 0) :
             
            # Update all multiples of p
            for i in range(2 * p, MAX, p):
                isPrime[i] = 1
 
def findSubset(a, n):
 
    cnt1 = 0
 
    # Counting no.of ones in the array
    for i in range(n): 
        if (a[i] == 1):
            cnt1+=1
 
    # Case-I: count of ones(1s) > 0 and 
    # an integer > 1 is present in the array
    if (cnt1 > 0):
 
        for i in range(n):
 
            # Find a[i], where a[i] + 1 is prime.
            if ((a[i] != 1) and
                (isPrime[a[i] + 1] == 0)):
 
                print(cnt1 + 1)
 
                # Print all the ones(1s).
                for j in range(cnt1):
                    print("1", end = " ")
 
                print(a[i])
                return 0
 
    # Case-II: array contains only ones(1s)
    if (cnt1 >= 2):
 
        print(cnt1)
 
        # Print all ones(1s).
        for i in range(cnt1):
            print("1", end = " ")
 
        print("\n")
        return 0
     
    # Case-III: array does not contain 1s
    for i in range(n):
        for j in range(i + 1, n):
             
            # Find a pair of integers whose 
            # sum is prime
            if (isPrime[a[i] + a[j]] == 0):
                print(2)
                print(a[i], " ", a[j])
 
    # Array contains only a single element.
    print(-1)
 
# Driver Code
sieve()
A =[ 2, 1, 1]
n =len(A)
findSubset(A, n)
 
# This code is contributed 
# by Mohit kumar 29

C#

// C# program to find a subset 
// in which sum of every pair 
// in it is a prime
using System;
 
class GFG
{
    static int MAX = 100001;
     
    static int []isPrime = new int[MAX];
     
    static int sieve()
    {
        for (int p = 2; 
                 p * p < MAX; p++) 
        {
            // If isPrime[p] is 
            // not changed, then
            // it is a prime
            if (isPrime[p] == 0) 
            {
                // Update all
                // multiples of p
                for (int i = p * 2; 
                         i < MAX; i += p)
                    isPrime[i] = 1;
            }
        }
        return -1;
    }     
    static int findSubset(int []a, int n)
    {
        int cnt1 = 0;
     
        // Counting no. of 
        // ones in the array
        for (int i = 0; i < n; i++) 
            if (a[i] == 1)
                cnt1++;
     
        // Case-I: count of 
        // ones(1s) > 0 and 
        // an integer > 1 is 
        // present in the array
        if (cnt1 > 0) 
        {
            for (int i = 0; i < n; i++) 
            {
                // Find a[i], where
                // a[i] + 1 is prime.
                if ((a[i] != 1) && 
                    (isPrime[a[i] + 1] == 0)) 
                {
                    Console.WriteLine(cnt1 + 1);
     
                    // Print all the ones(1s).
                    for (int j = 0; j < cnt1; j++) 
             
                    Console.Write(1 + " ");
                    Console.WriteLine(a[i]); // print a[i].
                    return 0;
                }
            }
        }
     
        // Case-II: array contains
        // only ones(1s)
        if (cnt1 >= 2) 
        {
            Console.WriteLine(cnt1);
     
            // Print all ones(1s).
            for (int i = 0; i < cnt1; i++) 
                Console.Write(1 + " ");
     
            Console.WriteLine();
            return 0;
        }
     
        // Case-III: array does
        // not contain 1s
        for (int i = 0; i < n; i++) 
        {
            for (int j = i + 1; j < n; j++) 
            {
                // Find a pair of integers
                // whose sum is prime
                if (isPrime[a[i] + a[j]] == 0) 
                {
                    Console.WriteLine(2);
                    Console.WriteLine(a[i] + " " + a[j]);
                    return 0;
                }
            }
        }
     
        // Array contains only 
        // a single element.
        Console.WriteLine(-1);
        return -1;
    }
     
    // Driver Code
    static void Main()
    {
        sieve();
        int []A = new int[]{ 2, 1, 1 };
        int n = A.Length;
        findSubset(A, n);
    }
}
 
// This code is contributed by 
// Manish Shaw(manishshaw1)

PHP

<?php
// PHP program to find 
// a subset in which 
// sum of every pair in
// it is a prime
$MAX = 100001;
 
$isPrime = array(); 
for($i = 0; 
    $i < $MAX; $i++)
    $isPrime[$i] = 0;
 
function sieve()
{
    global $MAX, $isPrime;
    for ($p = 2; 
         $p * $p < $MAX; $p++) 
    {
        // If isPrime[p] is not 
        // changed, then it is
        // a prime
        if ($isPrime[$p] == 0) 
        {
            // Update all
            // multiples of p
            for ($i = $p * 2; 
                 $i < $MAX; $i += $p)
                $isPrime[$i] = 1;
        }
    }
}
 
function findSubset($a, $n)
{
    $cnt1 = 0;
    global $MAX, $isPrime;
     
    // Counting no.of 
    // ones in the array
    for ($i = 0; $i < $n; $i++) 
        if ($a[$i] == 1)
            $cnt1++;
 
    // Case-I: count of 
    // ones(1s) > 0 and 
    // an integer > 1 is 
    // present in the array
    if ($cnt1 > 0) 
    {
        for ($i = 0; $i < $n; $i++) 
        {
            // Find a[i], where 
            // a[i] + 1 is prime.
            if (($a[$i] != 1) and
                ($isPrime[$a[$i] + 1] == 0)) 
            {
                echo (($cnt1 + 1) . "\n");
 
                // Print $all the ones(1s).
                for ($j = 0;
                     $j < $cnt1; $j++) 
                {
                    echo ("1 ");
                }
                echo ($a[$i] . "\n");
                return 0;
            }
        }
    }
 
    // Case-II: array contains 
    // only ones(1s)
    if ($cnt1 >= 2) 
    {
        echo (cnt1 . "\n");
 
        // Print $all ones(1s).
        for ($i = 0; 
             $i < $cnt1; $i++) 
            echo ("1 ");
 
        echo ("\n");
        return 0;
    } 
     
    // Case-III: array does 
    // not contain 1s
    for ($i = 0; $i < $n; $i++) 
    {
        for ($j = $i + 1;
             $j < $n; $j++) 
        {
            // Find a pair of integers
            // whose sum is prime
            if ($isPrime[$a[$i] + 
                $a[$j]] == 0) 
            {
                echo (2 . "\n");
                echo ($a[$i] . " " . 
                      $a[$j] . "\n");
                return 0;
            }
        }
    }
 
    // Array contains only
    // a single element.
    echo (-1 . "\n");
}
 
// Driver Code
sieve();
$A = array(2, 1, 1);
$n = count($A);
findSubset($A, $n);
 
// This code is contributed by 
// Manish Shaw(manishshaw1)
?>

Javascript

<script>
 
// JavaScript program to find a 
// subset in which sum of 
// every pair in it is a prime
     
    let MAX = 100001;
    let isPrime = new Array(MAX);
    for(let i=0;i<MAX;i++)
    {
        isPrime[i]=0;
    }
     
    function sieve()
    {
        for (let p = 2; 
                 p * p < MAX; p++) 
        {
            // If isPrime[p] is 
            // not changed, then
            // it is a prime
            if (isPrime[p] == 0) 
            {
                // Update all
                // multiples of p
                for (let i = p * 2; 
                         i < MAX; i += p)
                    isPrime[i] = 1;
            }
        }
        return -1;
    }
     
    function findSubset(a,n)
    {
        let cnt1 = 0;
       
        // Counting no. of 
        // ones in the array
        for (let i = 0; i < n; i++) 
            if (a[i] == 1)
                cnt1++;
       
        // Case-I: count of 
        // ones(1s) > 0 and 
        // an integer > 1 is 
        // present in the array
        if (cnt1 > 0) 
        {
            for (let i = 0; i < n; i++) 
            {
                // Find a[i], where
                // a[i] + 1 is prime.
                if ((a[i] != 1) && 
                    (isPrime[a[i] + 1] == 0)) 
                {
                    document.write((cnt1 + 1)+"<br>");
       
                    // Print all 
                    // the ones(1s).
                    for (let j = 0;
                             j < cnt1; j++) 
               
                    document.write(1 + " ");
                    // print a[i].
                    document.write(a[i]+"<br>"); 
                    return 0;
                }
            }
        }
       
        // Case-II: array contains
        // only ones(1s)
        if (cnt1 >= 2) 
        {
            document.write(cnt1);
       
            // Print all ones(1s).
            for (let i = 0; 
                     i < cnt1; i++) 
                document.write(1 + " ");
       
            document.write("<br>");
            return 0;
        }
       
        // Case-III: array does
        // not contain 1s
        for (let i = 0; i < n; i++) 
        {
            for (let j = i + 1; 
                     j < n; j++) 
            {
                // Find a pair of integers
                // whose sum is prime
                if (isPrime[a[i] + a[j]] == 0) 
                {
                    document.write(2+"<br>");
                    document.write(a[i] +
                                 " " + a[j]+"<br>");
                    return 0;
                }
            }
        }
       
        // Array contains only 
        // a single element.
        document.write(-1);
        return -1;
    }
     
    // Driver Code
    sieve();
    let A=[2, 1, 1 ];
    let n = A.length;
    findSubset(A, n);
 
// This code is contributed by unknown2108
 
</script>

Output:

3
1 1 2

Time Complexity : O(n²)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!