Dada una array. La tarea es contar los posibles pares que se pueden formar usando los elementos de la array donde ambos elementos del par son primos.
Nota : Los pares como (a, b) y (b, a) no deben considerarse diferentes.
Ejemplos:
Input: arr[] = {1, 2, 3, 5, 7, 9}
Output: 6
From the given array, prime pairs are
(2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)
Input: arr[] = {1, 4, 5, 9, 11}
Output: 1
Un enfoque ingenuo es contar todos los pares posibles en la array y verificar si ambos elementos en el par son primos.
Un enfoque eficiente es contar una cantidad de números primos en la array utilizando el Tamiz de Eratóstenes. Sea C. Ahora, el número total de pares posibles es igual a C*(C-1)/2.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find count of
// prime pairs in given array.
#include <bits/stdc++.h>
using namespace std;
// Function to find count of prime pairs
int pairCount(int arr[], int n)
{
// Find maximum value in the array
int max_val = *max_element(arr, arr + n);
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
vector<bool> prime(max_val + 1, true);
// Remaining part of SIEVE
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= max_val; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p)
prime[i] = false;
}
}
// Find all primes in arr[]
int count = 0;
for (int i = 0; i < n; i++)
if (prime[arr[i]])
count++;
// return the count of
// possible prime pairs
// Number of unique pairs
// with N elements is N*(N-1)/2
return (count * (count - 1)) / 2;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << pairCount(arr, n);
return 0;
}
Java
// Java program to find count of
// prime pairs in given array.
import java.util.*;
class GFG {
// Function to find count of prime pairs
static int pairCount(int arr[], int n)
{
// Find maximum value in the array
int max_val = Arrays.stream(arr).max().getAsInt();
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
Vector<Boolean> prime = new Vector<>(max_val + 1);
for (int i = 0; i < max_val + 1; i++) {
prime.add(true);
}
// Remaining part of SIEVE
prime.add(0, Boolean.FALSE);
prime.add(1, Boolean.FALSE);
for (int p = 2; p * p <= max_val; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime.get(p) == true) {
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p) {
prime.add(i, Boolean.FALSE);
}
}
}
// Find all primes in arr[]
int count = 0;
for (int i = 0; i < n; i++) {
if (prime.get(arr[i])) {
count++;
}
}
// return the count of
// possible prime pairs
// Number of unique pairs
// with N elements is N*(N-1)/2
return (count * (count - 1)) / 2;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = arr.length;
System.out.println(pairCount(arr, n));
}
}
/* This code has been contributed
by PrinciRaj1992*/
Python3
# Python 3 program to find count of # prime pairs in given array. from math import sqrt # Function to find count of prime pairs def pairCount(arr, n): # Find maximum value in the array max_val = arr[0] for i in range(len(arr)): if(arr[i] > max_val): max_val = arr[i] # USE SIEVE TO FIND ALL PRIME NUMBERS # LESS THAN OR EQUAL TO max_val # Create a boolean array "prime[0..n]". # A value in prime[i] will finally be # false if i is Not a prime, else true. prime = [True for i in range(max_val + 1)] # Remaining part of SIEVE prime[0] = False prime[1] = False k = int(sqrt(max_val)) + 1 for p in range(2, k, 1): # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples of p for i in range(p * 2, max_val + 1, p): prime[i] = False # Find all primes in arr[] count = 0 for i in range(0, n, 1): if (prime[arr[i]]): count += 1 # return the count of possible prime # pairs. Number of unique pairs # with N elements is N*(N-1)/2 return (count * (count - 1)) / 2 # Driver code if __name__ =='__main__': arr = [1, 2, 3, 4, 5, 6, 7] n = len(arr) print(int(pairCount(arr, n))) # This code is contributed by # Shahshank_Sharma
C#
// C# program to find count of
// prime pairs in given array.
using System;
using System.Linq;
class GFG {
// Function to find count of prime pairs
static int pairCount(int[] arr, int n)
{
// Find maximum value in the array
int max_val = arr.Max();
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
bool[] prime = new bool[max_val + 1];
for (int i = 0; i < max_val + 1; i++) {
prime[i] = true;
}
// Remaining part of SIEVE
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= max_val; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p) {
prime[i] = false;
}
}
}
// Find all primes in arr[]
int count = 0;
for (int i = 0; i < n; i++) {
if (prime[arr[i]]) {
count++;
}
}
// return the count of
// possible prime pairs
// Number of unique pairs
// with N elements is N*(N-1)/2
return (count * (count - 1)) / 2;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
int n = arr.Length;
Console.WriteLine(pairCount(arr, n));
}
}
// This code has been contributed by ihritik
PHP
<?php
// PHP program to find count of
// prime pairs in given array.
// Function to find count of prime pairs
function pairCount($arr, $n)
{
// Find maximum value in the array
$max_val = max($arr);
// USE SIEVE TO FIND ALL PRIME NUMBERS
// LESS THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]".
// A value in prime[i] will finally be
// false if i is Not a prime, else true.
// vector<bool> prime(max_val + 1, true);
$prime = array_fill(0, $max_val + 1, true);
// Remaining part of SIEVE
$prime[0] = false;
$prime[1] = false;
for ($p = 2; $p * $p <= $max_val; $p++)
{
// If prime[p] is not changed,
// then it is a prime
if ($prime[$p] == true)
{
// Update all multiples of p
for ($i = $p * 2;
$i <= $max_val; $i += $p)
$prime[$i] = false;
}
}
// Find all primes in arr[]
$count = 0;
for ($i = 0; $i < $n; $i++)
if ($prime[$arr[$i]])
$count++;
// return the count of
// possible prime pairs
// Number of unique pairs
// with N elements is N*(N-1)/2
return ($count * ($count - 1)) / 2;
}
// Driver code
$arr = array (1, 2, 3, 4, 5, 6, 7 );
$n = sizeof($arr);
echo pairCount($arr, $n);
// This code is contributed by ajit...
?>
Javascript
<script>
// Javascript program to find count of
// prime pairs in given array.
// Function to find count of prime pairs
function pairCount(arr, n)
{
// Find maximum value in the array
let max_val = 0;
for (let i = 0; i < n; i++)
{
max_val = Math.max(max_val, arr[i]);
}
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
let prime = new Array(max_val + 1);
for (let i = 0; i < max_val + 1; i++) {
prime[i] = true;
}
// Remaining part of SIEVE
prime[0] = false;
prime[1] = false;
for (let p = 2; p * p <= max_val; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (let i = p * 2; i <= max_val; i += p)
{
prime[i] = false;
}
}
}
// Find all primes in arr[]
let count = 0;
for (let i = 0; i < n; i++) {
if (prime[arr[i]]) {
count++;
}
}
// return the count of
// possible prime pairs
// Number of unique pairs
// with N elements is N*(N-1)/2
return (count * (count - 1)) / 2;
}
let arr = [ 1, 2, 3, 4, 5, 6, 7 ];
let n = arr.length;
document.write(pairCount(arr, n));
</script>
Producción:
6