Zählen Sie Sexy Prime Pairs im angegebenen Array

Bei einem gegebenen Array arr[] der Größe N , das natürliche Zahlen enthält, besteht die Aufgabe darin, alle möglichen Paare in arr[] zu zählen, die Sexy Prime Pairs sind .

Ein SPP (Sexy Prime Pair) sind die Zahlen, die Primzahlen sind und eine Differenz von 6 zwischen den Primzahlen haben. Mit anderen Worten, ein SPP (Sexy Prime Pair) ist eine Primzahl mit einer Primzahllücke von sechs.

Beispiele:

Eingabe: arr[] = { 6, 7, 5, 11, 13 }
Ausgabe: 2
Erklärung:
Die 2 Paare sind (5, 11) und (7, 13).
Eingabe: arr[] = { 2, 4, 6, 11 }
Ausgabe: 0
Erklärung:
Es gibt keine solchen Paare, die SPP (Sexy Prime Pair) bilden.

Naiver Ansatz: Um das oben erwähnte Problem zu lösen, besteht die Idee darin, alle möglichen Paare im gegebenen Array arr[] zu finden und zu prüfen, ob beide Elemente in Paaren Primzahlen sind und sich um 6 unterscheiden , dann bilden die aktuellen Paare SPP (Sexy Prime Paar) .
Unten ist die Implementierung des obigen Ansatzes:

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>

Ausgabe:

Zeitkomplexität: O(sqrt(M) * N ² ), wobei N die Anzahl der Elemente im gegebenen Array und M das maximale Element im Array ist.
Effizienter Ansatz:
Die oben genannte Methode kann durch folgende Schritte optimiert werden:

Berechnen Sie alle Primzahlen bis zur maximalen Zahl im gegebenen Array arr[] mit Sieve of Eratosthenes vor .
Speichern Sie die gesamte Häufigkeit aller Elemente für das angegebene Array und sortieren Sie das Array.
Überprüfen Sie für jedes Element im Array, ob das Element eine Primzahl ist oder nicht.
Wenn das Element eine Primzahl ist, prüfen Sie, ob (Element + 6) eine Primzahl ist oder nicht und im angegebenen Array vorhanden ist.
Wenn (Element + 6) vorhanden ist, ergibt die Häufigkeit von (Element + 6) die Anzahl der Paare für das aktuelle Element.
Wiederholen Sie den obigen Schritt für alle Elemente im Array.

Unten ist die Implementierung des obigen Ansatzes:

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>

Ausgabe:

Zeitkomplexität: O(N * sqrt(M)), wobei N die Anzahl der Elemente im angegebenen Array und M das maximale Element im Array ist.
Nebenraumkomplexität: O(N)

Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .

Acervo Lima

Die größte Sammlung von Tutorials und Referenzen

Zählen Sie Sexy Prime Pairs im angegebenen Array

C++

Java

Python 3

C#

Javascript

C++

Java

Python3

C#

Javascript

Latest posts

C++

Java

Python 3

C#

Javascript

C++

Java

Python3

C#

Javascript

Latest posts

Most popular posts