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: 2
Explicación:
Los 2 pares son (5, 11) y (7, 13).
Entrada: arr[] = { 2, 4, 6, 11 }
Salida: 0
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:
- Precalcule todos los números primos hasta el número máximo en la array dada arr[] usando Sieve of Eratosthenes .
- Almacene toda la frecuencia de todos los elementos para la array dada y ordene la array.
- Para cada elemento de la array, compruebe si el elemento es primo o no.
- Si el elemento es primo, compruebe si (elemento + 6) es un número primo o no y está presente en la array dada.
- Si el (elemento + 6) está presente, entonces la frecuencia de (elemento + 6) dará el conteo de pares para el elemento actual.
- 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)