Cuente los pares principales atractivos en la array dada

Dada una array arr[] de tamaño N que contiene números naturales, la tarea es contar todos los pares posibles en la arr[] que son Sexy Prime Pairs .
 

Un SPP (Sexy Prime Pair) son aquellos números que son primos y tienen una diferencia de 6 entre los números primos. En otras palabras, un SPP (Sexy Prime Pair) es un número primo que tiene un espacio entre números primos de seis.

Ejemplos: 
 

Entrada: arr[] = { 6, 7, 5, 11, 13 } 
Salida:
Explicación: 
Los 2 pares son (5, 11) y (7, 13).
Entrada: arr[] = { 2, 4, 6, 11 } 
Salida:
Explicación: 
No existen tales pares que formen SPP (Sexy Prime Pair). 
 

Enfoque ingenuo: para resolver el problema mencionado anteriormente, la idea es encontrar todos los pares posibles en la array dada arr[] y verificar si ambos elementos en pares son números primos y difieren en 6 , luego los pares actuales forman SPP (Sexy Prime pareja) .
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program to count Sexy
// Prime pairs in array
 
#include <bits/stdc++.h>
using namespace std;
 
// A utility function to check if
// the number n is prime or not
bool isPrime(int n)
{
    // Base Cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // Check to skip middle five
    // numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i += 6) {
 
        // If n is divisible by i and i+2
        // then it is not prime
        if (n % i == 0
            || n % (i + 6) == 0) {
            return false;
        }
    }
 
    return true;
}
 
// A utility function that check
// if n1 and n2 are SPP (Sexy Prime Pair)
// or not
bool SexyPrime(int n1, int n2)
{
    return (isPrime(n1)
            && isPrime(n2)
            && abs(n1 - n2) == 6);
}
 
// Function to find SPP (Sexy Prime Pair)
// pairs from the given array
int countSexyPairs(int arr[], int n)
{
    int count = 0;
 
    // Iterate through all pairs
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
 
            // Increment count if
            // SPP (Sexy Prime Pair) pair
            if (SexyPrime(arr[i], arr[j])) {
                count++;
            }
        }
    }
 
    return count;
}
 
// Driver code
int main()
{
    int arr[] = { 6, 7, 5, 11, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to find
    // SPP (Sexy Prime Pair) pair
    cout << countSexyPairs(arr, n);
    return 0;
}

Java

// Java program to count Sexy
// Prime pairs in array
import java.util.*;
 
class GFG {
 
    // A utility function to check if
    // the number n is prime or not
    static boolean isPrime(int n)
    {
        // Base Cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // Check to skip middle five
        // numbers in below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i * i <= n; i += 6) {
 
            // If n is divisible by i and i+2
            // then it is not prime
            if (n % i == 0 || n % (i + 6) == 0) {
                return false;
            }
        }
 
        return true;
    }
 
    // A utility function that check
    // if n1 and n2 are SPP (Sexy Prime Pair)
    // or not
    static boolean SexyPrime(int n1, int n2)
    {
        return (isPrime(n1)
                && isPrime(n2)
                && Math.abs(n1 - n2) == 6);
    }
 
    // Function to find SPP (Sexy Prime Pair)
    // pairs from the given array
    static int countSexyPairs(int arr[], int n)
    {
        int count = 0;
 
        // Iterate through all pairs
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
 
                // Increment count if
                // SPP (Sexy Prime Pair) pair
                if (SexyPrime(arr[i], arr[j])) {
                    count++;
                }
            }
        }
 
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 6, 7, 5, 11, 13 };
        int n = arr.length;
 
        // Function call to find
        // SPP (Sexy Prime Pair) pair
        System.out.print(
            countSexyPairs(arr, n));
    }
}

Python 3

# Python 3 program to count Sexy
# Prime pairs in array
from math import sqrt
 
# A utility function to check if
# the number n is prime or not
def isPrime(n):
     
    # Base Cases
    if (n <= 1):
        return False
    if (n <= 3):
        return True
 
    # Check to skip middle five
    # numbers in below loop
    if (n % 2 == 0 or n % 3 == 0):
        return False
 
    for i in range(5, int(sqrt(n))+1, 6):
         
        # If n is divisible by i and i + 2
        # then it is not prime
        if (n % i == 0 or n % (i + 6) == 0):
            return False
 
    return True
 
# A utility function that check
# if n1 and n2 are SPP (Sexy Prime Pair)
# or not
def SexyPrime(n1, n2):
    return (isPrime(n1)
           and isPrime(n2)
           and abs(n1 - n2) == 6)
 
# Function to find SPP (Sexy Prime Pair)
# pairs from the given array
def countSexyPairs(arr, n):
    count = 0
 
    # Iterate through all pairs
    for i in range(n):
        for j in range(i + 1, n):
             
            # Increment count if
            # SPP (Sexy Prime Pair) pair
            if (SexyPrime(arr[i], arr[j])):
                count += 1
 
    return count
 
# Driver code
if __name__ == '__main__':
    arr = [6, 7, 5, 11, 13]
    n = len(arr)
 
    # Function call to find
    # SPP (Sexy Prime Pair) pair
    print(countSexyPairs(arr, n))

C#

// C# program to count Sexy
// Prime pairs in array
using System;
 
class GFG {
 
    // A utility function to check if
    // the number n is prime or not
    static bool isPrime(int n)
    {
        // Base Cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // Check to skip middle five
        // numbers in below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i * i <= n; i += 6) {
 
            // If n is divisible by i and i+2
            // then it is not prime
            if (n % i == 0
                || n % (i + 6) == 0) {
                return false;
            }
        }
 
        return true;
    }
 
    // A utility function that check
    // if n1 and n2 are SPP (Sexy Prime Pair)
    // or not
    static bool SexyPrime(int n1, int n2)
    {
        return (isPrime(n1)
                && isPrime(n2)
                && Math.Abs(n1 - n2) == 6);
    }
 
    // Function to find SPP (Sexy Prime Pair)
    // pairs from the given array
    static int countSexyPairs(int[] arr, int n)
    {
        int count = 0;
 
        // Iterate through all pairs
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
 
                // Increment count if
                // SPP (Sexy Prime Pair) pair
                if (SexyPrime(arr[i], arr[j])) {
                    count++;
                }
            }
        }
 
        return count;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] arr = { 6, 7, 5, 11, 13 };
        int n = arr.Length;
 
        // Function call to find
        // SPP (Sexy Prime Pair) pair
        Console.Write(countSexyPairs(arr, n));
    }
}

Javascript

<script>
 
// javascript program to count Sexy
// Prime pairs in array
 
 
    // A utility function to check if
    // the number n is prime or not
     
    function isPrime( n)
    {
        // Base Cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // Check to skip middle five
        // numbers in below loop
         
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (var i = 5; i * i <= n; i += 6) {
 
            // If n is divisible by i and i+2
            // then it is not prime
            if (n % i == 0
                || n % (i + 6) == 0) {
                return false;
            }
        }
 
        return true;
    }
 
    // A utility function that check
    // if n1 and n2 are SPP (Sexy Prime Pair)
    // or not
     
    function SexyPrime( n1,  n2)
    {
        return (isPrime(n1)
                && isPrime(n2)
                && Math.abs(n1 - n2) == 6);
    }
 
    // Function to find SPP (Sexy Prime Pair)
    // pairs from the given array
    function countSexyPairs( arr,  n)
    {
        var count = 0;
 
        // Iterate through all pairs
        for (var i = 0; i < n; i++) {
            for (var j = i + 1; j < n; j++) {
 
                // Increment count if
                // SPP (Sexy Prime Pair) pair
                if (SexyPrime(arr[i], arr[j])) {
                    count++;
                }
            }
        }
 
        return count;
    }
 
    // Driver code
 
        var arr = [ 6, 7, 5, 11, 13 ]
        var n = arr.length;
 
        // Function call to find
        // SPP (Sexy Prime Pair) pair
        document.write(countSexyPairs(arr, n));
         
</script>
Producción: 

2

 

Complejidad de tiempo: O(sqrt(M) * N 2 ), donde N es el número de elementos en la array dada y M es el elemento máximo en la array.
Enfoque eficiente:
el método mencionado anteriormente se puede optimizar mediante los siguientes pasos: 
 

  1. Precalcule todos los números primos hasta el número máximo en la array dada arr[] usando Sieve of Eratosthenes .
  2. Almacene toda la frecuencia de todos los elementos para la array dada y ordene la array.
  3. Para cada elemento de la array, compruebe si el elemento es primo o no.
  4. Si el elemento es primo, compruebe si (elemento + 6) es un número primo o no y está presente en la array dada.
  5. Si el (elemento + 6) está presente, entonces la frecuencia de (elemento + 6) dará el conteo de pares para el elemento actual.
  6. Repita el paso anterior para todos los elementos de la array.

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program to count Sexy
// Prime pairs in array
 
#include <bits/stdc++.h>
using namespace std;
 
// To store check the prime
// number
vector<bool> Prime;
 
// A utility function that find
// the Prime Numbers till N
void computePrime(int N)
{
 
    // Resize the Prime Number
    Prime.resize(N + 1, true);
    Prime[0] = Prime[1] = false;
 
    // Loop till sqrt(N) to find
    // prime numbers and make their
    // multiple false in the bool
    // array Prime
    for (int i = 2; i * i <= N; i++) {
        if (Prime[i]) {
            for (int j = i * i; j < N; j += i) {
                Prime[j] = false;
            }
        }
    }
}
 
// Function that returns the count
// of SPP (Sexy Prime Pair) Pairs
int countSexyPairs(int arr[], int n)
{
 
    // Find the maximum element in
    // the given array arr[]
    int maxE = *max_element(arr, arr + n);
 
    // Function to calculate the
    // prime numbers till N
    computePrime(maxE);
 
    // To store the count of pairs
    int count = 0;
 
    // To store the frequency of
    // element in the array arr[]
    int freq[maxE + 1] = { 0 };
 
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }
 
    // Sort before traversing the array
    sort(arr, arr + n);
 
    // Traverse the array and find
    // the pairs with SPP (Sexy Prime Pair)
    for (int i = 0; i < n; i++) {
 
        // If current element is
        // Prime, then check for
        // (current element + 6)
        if (Prime[arr[i]]) {
            if (freq[arr[i] + 6] > 0
                && Prime[arr[i] + 6]) {
                count++;
            }
        }
    }
 
    // Return the count of pairs
    return count;
}
 
// Driver code
int main()
{
    int arr[] = { 6, 7, 5, 11, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to find
    // SPP (Sexy Prime Pair) pair
    cout << countSexyPairs(arr, n);
    return 0;
}

Java

// Java program to count Sexy
// Prime pairs in array
 
import java.util.*;
 
class GFG {
 
    // To store check the prime
    // number
    static boolean[] Prime;
 
    // A utility function that find
    // the Prime Numbers till N
    static void computePrime(int N)
    {
 
        // Resize the Prime Number
        Prime = new boolean[N + 1];
        Arrays.fill(Prime, true);
        Prime[0] = Prime[1] = false;
 
        // Loop till Math.sqrt(N) to find
        // prime numbers and make their
        // multiple false in the bool
        // array Prime
        for (int i = 2; i * i <= N; i++) {
            if (Prime[i]) {
                for (int j = i * i; j < N; j += i) {
                    Prime[j] = false;
                }
            }
        }
    }
 
    // Function that returns the count
    // of SPP (Sexy Prime Pair) Pairs
    static int countSexyPairs(int arr[], int n)
    {
 
        // Find the maximum element in
        // the given array arr[]
        int maxE = Arrays.stream(arr)
                       .max()
                       .getAsInt();
 
        // Function to calculate the
        // prime numbers till N
        computePrime(maxE);
 
        // To store the count of pairs
        int count = 0;
 
        // To store the frequency of
        // element in the array arr[]
        int freq[] = new int[maxE + 1];
 
        for (int i = 0; i < n; i++) {
            freq[arr[i]]++;
        }
 
        // Sort before traversing the array
        Arrays.sort(arr);
 
        // Traverse the array and find
        // the pairs with SPP (Sexy Prime Pair)
        for (int i = 0; i < n; i++) {
 
            // If current element is
            // Prime, then check for
            // (current element + 6)
            if (Prime[arr[i]]) {
                if (arr[i] + 6 < freq.length
                    && freq[arr[i] + 6] > 0
                    && Prime[arr[i] + 6]) {
                    count++;
                }
            }
        }
 
        // Return the count of pairs
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 6, 7, 5, 11, 13 };
        int n = arr.length;
 
        // Function call to find
        // SPP (Sexy Prime Pair) pair
        System.out.print(
            countSexyPairs(arr, n));
    }
}

Python3

# Python 3 program to count Sexy
# Prime pairs in array
 
# A utility function that find
# the Prime Numbers till N
def computePrime( N):
 
    # Resize the Prime Number
    Prime = [True]*(N + 1)
    Prime[0] = False
    Prime[1] = False
 
    # Loop till sqrt(N) to find
    # prime numbers and make their
    # multiple false in the bool
    # array Prime
    i = 2
    while i * i <= N:
        if (Prime[i]):
            for j in range( i * i, N, i):
                Prime[j] = False
        i += 1
 
    return Prime
 
# Function that returns the count
# of SPP (Sexy Prime Pair) Pairs
def countSexyPairs(arr, n):
 
    # Find the maximum element in
    # the given array arr[]
    maxE = max(arr)
 
    # Function to calculate the
    # prime numbers till N
    Prime = computePrime(maxE)
 
    # To store the count of pairs
    count = 0
 
    # To store the frequency of
    # element in the array arr[]
    freq = [0]*(maxE + 6)
 
    for i in range( n):
        freq[arr[i]] += 1
 
    # Sort before traversing the array
    arr.sort()
 
    # Traverse the array and find
    # the pairs with SPP (Sexy Prime Pair)s
    for i in range(n):
 
        # If current element is
        # Prime, then check for
        # (current element + 6)
        if (Prime[arr[i]]):
            if ((arr[i] + 6) <= (maxE)
                and freq[arr[i] + 6] > 0
                and Prime[arr[i] + 6]):
                count += 1
 
    # Return the count of pairs
    return count
 
# Driver code
if __name__ == "__main__":
     
    arr = [ 6, 7, 5, 11, 13 ]
    n = len(arr)
 
    # Function call to find
    # SPP (Sexy Prime Pair)s pair
    print( countSexyPairs(arr, n))
    

C#

// C# program to count Sexy
// Prime pairs in array
 
using System;
using System.Linq;
 
class GFG {
 
    // To store check the prime
    // number
    static bool[] Prime;
 
    // A utility function that find
    // the Prime Numbers till N
    static void computePrime(int N)
    {
 
        // Resize the Prime Number
        Prime = new bool[N + 1];
        for (int i = 0; i <= N; i++) {
            Prime[i] = true;
        }
 
        Prime[0] = Prime[1] = false;
 
        // Loop till Math.Sqrt(N) to find
        // prime numbers and make their
        // multiple false in the bool
        // array Prime
        for (int i = 2; i * i <= N; i++) {
            if (Prime[i]) {
                for (int j = i * i; j < N; j += i) {
                    Prime[j] = false;
                }
            }
        }
    }
 
    // Function that returns the count
    // of SPP (Sexy Prime Pair) Pairs
    static int countSexyPairs(int[] arr, int n)
    {
 
        // Find the maximum element in
        // the given array []arr
        int maxE = arr.Max();
 
        // Function to calculate the
        // prime numbers till N
        computePrime(maxE);
 
        // To store the count of pairs
        int count = 0;
 
        // To store the frequency of
        // element in the array []arr
        int[] freq = new int[maxE + 1];
 
        for (int i = 0; i < n; i++) {
            freq[arr[i]]++;
        }
 
        // Sort before traversing the array
        Array.Sort(arr);
 
        // Traverse the array and find
        // the pairs with SPP (Sexy Prime Pair)s
        for (int i = 0; i < n; i++) {
 
            // If current element is
            // Prime, then check for
            // (current element + 6)
            if (Prime[arr[i]]) {
                if (arr[i] + 6 < freq.Length
                    && freq[arr[i] + 6] > 0
                    && Prime[arr[i] + 6]) {
                    count++;
                }
            }
        }
 
        // Return the count of pairs
        return count;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] arr = { 6, 7, 5, 11, 13 };
        int n = arr.Length;
 
        // Function call to find
        // SPP (Sexy Prime Pair)s pair
        Console.Write(countSexyPairs(arr, n));
    }
}

Javascript

<script>
 
// javascript program to count Sexy
// Prime pairs in array
 
// To store check the prime
// number
var Prime = Array(100).fill(true);
 
// A utility function that find
// the Prime Numbers till N
function computePrime(N)
{
       
     var i,j;
    // Resize the Prime Number]
    Prime[0] = Prime[1] = false;
 
    // Loop till sqrt(N) to find
    // prime numbers and make their
    // multiple false in the bool
    // array Prime
    for (i = 2; i * i <= N; i++) {
        if (Prime[i]) {
            for (j = i * i; j < N; j += i) {
                Prime[j] = false;
            }
        }
    }
}
 
// Function that returns the count
// of SPP (Sexy Prime Pair) Pairs
function countSexyPairs(arr, n)
{
 
    // Find the maximum element in
    // the given array arr[]
    var maxE = Math.max.apply(Math, arr);
 
    // Function to calculate the
    // prime numbers till N
    computePrime(maxE);
 
    // To store the count of pairs
    var count = 0;
 
    // To store the frequency of
    // element in the array arr[]
    var freq = Array(maxE + 1).fill(0);
 
    for (i = 0; i < n; i++) {
        freq[arr[i]]++;
    }
 
    // Sort before traversing the array
    arr.sort();
 
    // Traverse the array and find
    // the pairs with SPP (Sexy Prime Pair)
    for (i = 0; i < n; i++) {
 
        // If current element is
        // Prime, then check for
        // (current element + 6)
        if (Prime[arr[i]]) {
            if (freq[arr[i] + 6] > 0
                && Prime[arr[i] + 6]) {
                count++;
            }
        }
    }
 
    // Return the count of pairs
    return count;
}
 
// Driver code
    var arr = [6, 7, 5, 11, 13];
    var n = arr.length;
 
    // Function call to find
    // SPP (Sexy Prime Pair) pair
    document.write(countSexyPairs(arr, n));
 
// This code is contributed by ipg2016107.
</script>
Producción: 

2

 

Complejidad de tiempo: O(N * sqrt(M)), donde N es el número de elementos en la array dada y M es el elemento máximo en la array.
Complejidad del espacio auxiliar: O(N)
 

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *