Dada una array A[], encuentre un subconjunto de tamaño máximo en el que la suma de cada par de elementos sea un número primo. Imprime su longitud y el subconjunto. Considere muchas consultas para diferentes arrays y el valor máximo de un elemento como 100000.
Ejemplos:
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).
Hagamos algunas observaciones y luego pasemos al problema. La suma de dos números es par si y solo ambos números son pares o impares. Un número par no puede ser un número primo excepto 2. Ahora, si tomamos tres números a, b y c, dos de ellos deben ser pares o impares (teorema de Pigeonhole). Entonces, nuestra solución existe solo en dos casos: (Deje que el subconjunto sea B)
- Caso I : Cuando B contiene solo dos números enteros (> 1) cuya suma es un número primo.
- Caso II : Cuando B contiene un número de unos (1) y otro número X, donde X + 1 debe ser un número primo (solo es posible cuando X es un número par).
Primero cuente el número de unos en la array usando un bucle for.
- Si el conteo de 1 es mayor que 0, recorra todo el arreglo y verifique si [A[i] + 1] es un número primo y (A[i] != 1), si encuentra alguno, imprima el tamaño de subarreglo como (cuenta de 1s) +1 y todos los unos(1s) y el A[i] encontrado. Salga del programa.
- Si el paso anterior falla (es decir, no se encuentra A[i]), imprima todos los unos (1). Salga del programa.
- Si el paso anterior falla (es decir, cuenta de 1s = 0 ), Verifique que cada par de elementos en la array su suma sea un número primo. Imprime 2 y el par de enteros.
- De lo contrario Imprimir -1.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
3 1 1 2
Complejidad del tiempo : O(n 2 )
Publicación traducida automáticamente
Artículo escrito por Harsha_Mogali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA