Given an array arr[] of size N containing natural numbers, the task is to count all possible pairs in the arr[] that are Sexy Prime Pairs.
A SPP (Sexy Prime Pair) are those numbers that are prime and having a difference 6 between the prime numbers. In other words, an SPP (Sexy Prime Pair) is a prime that has a prime gap of six.
Examples:
Input: arr[] = { 6, 7, 5, 11, 13 }
Output: 2
Explanation:
The 2 pairs are (5, 11) and (7, 13).
Input: arr[] = { 2, 4, 6, 11 }
Output: 0
Explanation:
There are no such pairs forming SPP (Sexy Prime Pair).
Naive Approach: To solve the problem mentioned above the idea is to find all possible pairs in the given array arr[] and check whether both the element in pairs are Prime Numbers and they differ by 6, then the current pairs form SPP (Sexy Prime Pair).
Below is the implementation of the above approach:
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 notbool 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 notbool 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 arrayint 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 codeint 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 arrayimport 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 arrayfrom math import sqrt# A utility function to check if# the number n is prime or notdef 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 notdef 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 arraydef 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 codeif __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 arrayusing 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> |
Output:
2
Time Complexity: O(sqrt(M) * N2), where N is the number of elements in the given array and M is the maximum element in the array.
Efficient Approach:
The method mentioned above can be optimized by the following steps:
- Precompute all the Prime Numbers till maximum number in the given array arr[] using Sieve of Eratosthenes.
- Store all the frequency of all element for the given array and sort the array.
- For each element in the array, check if the element is prime or not.
- If the element is prime, then check if (element + 6) is a prime number or not and is present in the given array.
- If the (element + 6) is present, then the frequency of (element + 6) will give the count of pairs for the current element.
- Repeat the above step for all the element in the array.
Below is the implementation of the above approach:
C++
// C++ program to count Sexy// Prime pairs in array#include <bits/stdc++.h>using namespace std;// To store check the prime// numbervector<bool> Prime;// A utility function that find// the Prime Numbers till Nvoid 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) Pairsint 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 codeint 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 arrayimport 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 Ndef 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) Pairsdef 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 codeif __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 arrayusing 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// numbervar Prime = Array(100).fill(true);// A utility function that find// the Prime Numbers till Nfunction 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) Pairsfunction 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> |
Output:
2
Time Complexity: O(N * sqrt(M)), where N is the number of elements in the given array, and M is the maximum element in the array.
Auxiliary Space Complexity: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
