Dada una array arr[] de elementos distintos, la tarea es contar el número total de pares distintos en los que al menos un elemento es primo.
Ejemplos:
Input: arr[] = {1, 3, 10, 7, 8}
Output: 7
Pairs with at least one prime are (1, 3), (1, 7),
(3, 1), (3, 7), (3, 8), (10, 7), (7, 8).
Input:arr[]={4, 6, 8, 2, 9};
Output: 4
Enfoque: Primero precalcule todos los números primos hasta el elemento Máximo de la array usando Sieve . Recorre todos y cada uno de los pares posibles y comprueba si alguno de los elementos del par es primo. Si es así, entonces incremente el conteo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find primes
void sieve(int maxm, int prime[])
{
prime[0] = prime[1] = 1;
for (int i = 2; i * i <= maxm; i++)
if (!prime[i])
for (int j = 2 * i; j <= maxm; j += i)
prime[j] = 1;
}
// Function to count the pair
int countPair(int a[], int n)
{
// Find the maximum element of the array
int maxm = *max_element(a, a + n);
int prime[maxm + 1];
memset(prime, 0, sizeof(prime));
// Find primes upto maximum
sieve(maxm, prime);
// Count pairs with at least prime
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (prime[a[i]] == 0 || prime[a[j]] == 0)
count++;
return count;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 5, 4, 7 };
int n = 5;
cout << countPair(arr, n);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// Function to find primes
static void sieve(int maxm, int prime[])
{
prime[0] = prime[1] = 1;
for (int i = 2; i * i <= maxm; i++)
if (prime[i] == 0)
for (int j = 2 * i; j <= maxm; j += i)
prime[j] = 1;
}
// Function to count the pair
static int countPair(int a[], int n)
{
// Find the maximum element of the array
int maxm = a[0];
for(int i = 1; i < n; i++)
if(a[i] > maxm)
maxm = a[i];
int [] prime = new int[maxm + 1];
for(int i = 0; i < maxm + 1; i++)
prime[i] = 0;
// Find primes upto maximum
sieve(maxm, prime);
// Count pairs with at least prime
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (prime[a[i]] == 0 || prime[a[j]] == 0)
count++;
return count;
}
// Driver code
public static void main(String []args)
{
int arr[] = { 2, 3, 5, 4, 7 };
int n = arr.length;
System.out.println(countPair(arr, n));
}
}
// This code is contributed by ihritik
Python3
# Python 3 implementation of the above approach from math import sqrt # Function to count the pair def countPair(a, n): # Find the maximum element of the array maxm = a[0] for i in range(len(a)): if(a[i] > maxm): maxm = a[i] prime = [0 for i in range(maxm + 1)] # Find primes upto maximum prime[0] = prime[1] = 1; for i in range(2, int(sqrt(maxm)) + 1, 1): if (prime[i] == 0): for j in range(2 * i, maxm + 1, i): prime[j] = 1 # Count pairs with at least prime count = 0 for i in range(n): for j in range(i + 1, n, 1): if (prime[a[i]] == 0 or prime[a[j]] == 0): count += 1 return count # Driver code if __name__ == '__main__': arr = [2, 3, 5, 4, 7] n = 5 print(countPair(arr, n)) # This code is contributed by # Sanjit_Prasad
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to find primes
static void sieve(int maxm, int []prime)
{
prime[0] = prime[1] = 1;
for (int i = 2; i * i <= maxm; i++)
if (prime[i] == 0)
for (int j = 2 * i; j <= maxm; j += i)
prime[j] = 1;
}
// Function to count the pair
static int countPair(int []a, int n)
{
// Find the maximum element of the array
int maxm = a[0];
for(int i = 1; i < n; i++)
if(a[i] > maxm)
maxm = a[i];
int [] prime = new int[maxm + 1];
for(int i = 0; i < maxm + 1; i++)
prime[i] = 0;
// Find primes upto maximum
sieve(maxm, prime);
// Count pairs with at least prime
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (prime[a[i]] == 0 || prime[a[j]] == 0)
count++;
return count;
}
// Driver code
public static void Main()
{
int []arr = { 2, 3, 5, 4, 7 };
int n = arr.Length;
Console.WriteLine(countPair(arr, n));
}
}
// This code is contributed by ihritik
PHP
<?php
// PHP implementation of the above approach
// Function to find primes
function sieve($maxm, $prime)
{
$prime[0] = $prime[1] = 1;
for ($i = 2; $i * $i <= $maxm; $i++)
if (!$prime[$i])
for ($j = 2 * $i;
$j <= $maxm; $j += $i)
$prime[$j] = 1;
}
// Function to count the pair
function countPair($a, $n)
{
// Find the maximum element of the array
$maxm = max($a);
$prime = array();
$prime = array_fill(0, $maxm + 1, 0);
// Find primes upto maximum
sieve($maxm, $prime);
// Count pairs with at least prime
$count = 0;
for ($i = 0; $i < $n; $i++)
for ($j = $i + 1; $j < $n; $j++)
if ($prime[$a[$i]] == 0 ||
$prime[$a[$j]] == 0)
$count++;
return $count;
}
// Driver code
$arr = array( 2, 3, 5, 4, 7 );
$n = 5;
echo countPair($arr, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the above approach
// Function to find primes
function sieve(maxm,prime)
{
prime[0] = prime[1] = 1;
for (let i = 2; i * i <= maxm; i++)
if (prime[i] == 0)
for (let j = 2 * i; j <= maxm; j += i)
prime[j] = 1;
}
// Function to count the pair
function countPair(a,n)
{
// Find the maximum element of the array
let maxm = a[0];
for(let i = 1; i < n; i++)
if(a[i] > maxm)
maxm = a[i];
let prime = new Array(maxm + 1);
for(let i = 0; i < maxm + 1; i++)
prime[i] = 0;
// Find primes upto maximum
sieve(maxm, prime);
// Count pairs with at least prime
let count = 0;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
if (prime[a[i]] == 0 || prime[a[j]] == 0)
count++;
return count;
}
// Driver code
let arr=[2, 3, 5, 4, 7];
let n = arr.length;
document.write(countPair(arr, n));
// This code is contributed by unknown2108
</script>
Producción:
10
Enfoque eficiente:
Enfoque: Primero precalcule todos los primos hasta el elemento Máximo de la array usando Sieve . Mantener el conteo de números primos y no primos. Luego cuente los pares con primos únicos, es decir , no primos * primos y cuente los pares con ambos primos (primos * (primos – 1)) / 2 . Devuelve la suma de ambos conteos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
// Function to find primes
void sieve(int maxm, int prime[])
{
prime[0] = prime[1] = 1;
for (int i = 2; i * i <= maxm; i++)
if (!prime[i])
for (int j = 2 * i; j <= maxm; j += i)
prime[j] = 1;
}
ll countPair(int a[], int n)
{
// Find the maximum element of the array
int maxm = *max_element(a, a + n);
int prime[maxm + 1];
memset(prime, 0, sizeof(prime));
// Find primes upto maximum
sieve(maxm, prime);
// Count number of primes
int countPrimes = 0;
for (int i = 0; i < n; i++)
if (prime[a[i]] == 0)
countPrimes++;
int nonPrimes = n - countPrimes;
ll pairswith1Prime = nonPrimes * countPrimes;
ll pairsWith2Primes = (countPrimes * (countPrimes - 1)) / 2;
return pairswith1Prime + pairsWith2Primes;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 5, 4, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countPair(arr, n);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// Function to find primes
static void sieve(int maxm, int []prime)
{
prime[0] = prime[1] = 1;
for (int i = 2; i * i <= maxm; i++)
if (prime[i]==0)
for (int j = 2 * i; j <= maxm; j += i)
prime[j] = 1;
}
static long countPair(int []a, int n)
{
// Find the maximum element of the array
int maxm = a[0];
int i;
for( i = 1; i < n ; i++)
if(a[i] > maxm)
maxm = a[i];
int [] prime = new int[maxm + 1];
for( i = 0; i < maxm + 1 ;i++)
prime[i] = 0;
// Find primes upto maximum
sieve(maxm, prime);
// Count number of primes
int countPrimes = 0;
for ( i = 0; i < n; i++)
if (prime[a[i]] == 0)
countPrimes++;
int nonPrimes = n - countPrimes;
long pairswith1Prime = nonPrimes *
countPrimes;
long pairsWith2Primes = (countPrimes *
(countPrimes - 1)) / 2;
return pairswith1Prime + pairsWith2Primes;
}
// Driver code
public static void main(String []args)
{
int [] arr = { 2, 3, 5, 4, 7 };
int n = arr.length;
System.out.println(countPair(arr, n));
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of the above approach # Function to find primes def sieve(maxm, prime): prime[0] = prime[1] = 1; i = 2; while (i * i <= maxm): if (prime[i] == 0): for j in range(2 * i, maxm + 1, i): prime[j] = 1; i += 1; def countPair(a, n): # Find the maximum element # of the array maxm = max(a); prime = [0] * (maxm + 1); # Find primes upto maximum sieve(maxm, prime); # Count number of primes countPrimes = 0; for i in range(n): if (prime[a[i]] == 0): countPrimes += 1; nonPrimes = n - countPrimes; pairswith1Prime = nonPrimes * countPrimes; pairsWith2Primes = (countPrimes * (countPrimes - 1)) // 2; return pairswith1Prime + pairsWith2Primes; # Driver code arr = [ 2, 3, 5, 4, 7 ]; n = len(arr); print(countPair(arr, n)); # This code is contributed by mits
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to find primes
static void sieve(int maxm, int []prime)
{
prime[0] = prime[1] = 1;
for (int i = 2; i * i <= maxm; i++)
if (prime[i] == 0)
for (int j = 2 * i; j <= maxm; j += i)
prime[j] = 1;
}
static long countPair(int []a, int n)
{
// Find the maximum element of the array
int maxm = a[0];
int i;
for( i = 1; i < n ;i++)
if(a[i] > maxm)
maxm = a[i];
int [] prime = new int[maxm + 1];
for( i = 0; i < maxm + 1 ;i++)
prime[i] = 0;
// Find primes upto maximum
sieve(maxm, prime);
// Count number of primes
int countPrimes = 0;
for ( i = 0; i < n; i++)
if (prime[a[i]] == 0)
countPrimes++;
int nonPrimes = n - countPrimes;
long pairswith1Prime = nonPrimes *
countPrimes;
long pairsWith2Primes = (countPrimes *
(countPrimes - 1)) / 2;
return pairswith1Prime + pairsWith2Primes;
}
// Driver code
public static void Main()
{
int [] arr = { 2, 3, 5, 4, 7 };
int n = arr.Length;
Console.WriteLine(countPair(arr, n));
}
}
// This code is contributed by ihritik
PHP
<?php
// PHP implementation of the above approach
// Function to find primes
function sieve($maxm, $prime)
{
$prime[0] = $prime[1] = 1;
for ($i = 2; $i * $i <= $maxm; $i++)
if (!$prime[$i])
for ($j = 2 * $i;
$j <= $maxm; $j += $i)
$prime[$j] = 1;
}
function countPair($a, $n)
{
// Find the maximum element
// of the array
$maxm = max($a);
$prime = array_fill(0, $maxm + 1,0);
// Find primes upto maximum
sieve($maxm, $prime);
// Count number of primes
$countPrimes = 0;
for ($i = 0; $i < $n; $i++)
if ($prime[$a[$i]] == 0)
$countPrimes++;
$nonPrimes = $n - $countPrimes;
$pairswith1Prime = $nonPrimes * $countPrimes;
$pairsWith2Primes = ($countPrimes *
($countPrimes - 1)) / 2;
return $pairswith1Prime + $pairsWith2Primes;
}
// Driver code
$arr = array( 2, 3, 5, 4, 7 );
$n = count($arr);
echo countPair($arr, $n);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript implementation of the above approach
// Function to find primes
function sieve(maxm, prime)
{
prime[0] = prime[1] = 1;
for (let i = 2; i * i <= maxm; i++)
if (prime[i] == 0)
for (let j = 2 * i; j <= maxm; j += i)
prime[j] = 1;
}
function countPair(a, n)
{
// Find the maximum element of the array
let maxm = a[0];
let i;
for( i = 1; i < n ;i++)
if(a[i] > maxm)
maxm = a[i];
let prime = new Array(maxm + 1);
for( i = 0; i < maxm + 1 ;i++)
prime[i] = 0;
// Find primes upto maximum
sieve(maxm, prime);
// Count number of primes
let countPrimes = 0;
for ( i = 0; i < n; i++)
if (prime[a[i]] == 0)
countPrimes++;
let nonPrimes = n - countPrimes;
let pairswith1Prime = nonPrimes * countPrimes;
let pairsWith2Primes = parseInt((countPrimes *
(countPrimes - 1)) / 2, 10);
return (pairswith1Prime + pairsWith2Primes);
}
let arr = [ 2, 3, 5, 4, 7 ];
let n = arr.length;
document.write(countPair(arr, n));
</script>
Producción:
10
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA