Given an array arr[] of distinct elements, the task is to count the total number of distinct pairs in which at least one element is prime.
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
Approach: First precompute all the prime till the Maximum element of array using Sieve . Traverse each and every possible pair and check if any of the elements in the pair is prime. If yes, then increment the count.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>
using namespace std;
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;
}
int countPair( int a[], int n)
{
int maxm = *max_element(a, a + n);
int prime[maxm + 1];
memset (prime, 0, sizeof (prime));
sieve(maxm, 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;
}
int main()
{
int arr[] = { 2, 3, 5, 4, 7 };
int n = 5;
cout << countPair(arr, n);
return 0;
}
|
Java
class GFG
{
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 int countPair( int a[], int n)
{
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 ;
sieve(maxm, 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;
}
public static void main(String []args)
{
int arr[] = { 2 , 3 , 5 , 4 , 7 };
int n = arr.length;
System.out.println(countPair(arr, n));
}
}
|
Python3
from math import sqrt
def countPair(a, n):
maxm = a[ 0 ]
for i in range ( len (a)):
if (a[i] > maxm):
maxm = a[i]
prime = [ 0 for i in range (maxm + 1 )]
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 = 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
if __name__ = = '__main__' :
arr = [ 2 , 3 , 5 , 4 , 7 ]
n = 5
print (countPair(arr, n))
|
C#
using System;
class GFG
{
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 int countPair( int []a, int n)
{
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;
sieve(maxm, 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;
}
public static void Main()
{
int []arr = { 2, 3, 5, 4, 7 };
int n = arr.Length;
Console.WriteLine(countPair(arr, n));
}
}
|
PHP
<?php
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 )
{
$maxm = max( $a );
$prime = array ();
$prime = array_fill (0, $maxm + 1, 0);
sieve( $maxm , $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 ;
}
$arr = array ( 2, 3, 5, 4, 7 );
$n = 5;
echo countPair( $arr , $n );
?>
|
Javascript
<script>
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)
{
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;
sieve(maxm, 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;
}
let arr=[2, 3, 5, 4, 7];
let n = arr.length;
document.write(countPair(arr, n));
</script>
|
Time Complexity: O(max(n2, m*log(log(m)))), where n is the size of the given array and m is the maximum element in the array.
Auxiliary Space: O(m), where m is the maximum element in the array.
Approach: First precompute all the prime till the Maximum element of array using Sieve . Maintain the count of primes and non-primes. Then count pairs with single prime i.e. nonPrimes * Primes and count pairs with both primes (Primes * (Primes – 1)) / 2. Return the sum of both counts.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
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)
{
int maxm = *max_element(a, a + n);
int prime[maxm + 1];
memset (prime, 0, sizeof (prime));
sieve(maxm, prime);
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;
}
int main()
{
int arr[] = { 2, 3, 5, 4, 7 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << countPair(arr, n);
return 0;
}
|
Java
class GFG
{
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)
{
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 ;
sieve(maxm, prime);
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;
}
public static void main(String []args)
{
int [] arr = { 2 , 3 , 5 , 4 , 7 };
int n = arr.length;
System.out.println(countPair(arr, n));
}
}
|
Python3
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):
maxm = max (a);
prime = [ 0 ] * (maxm + 1 );
sieve(maxm, prime);
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;
arr = [ 2 , 3 , 5 , 4 , 7 ];
n = len (arr);
print (countPair(arr, n));
|
C#
using System;
class GFG
{
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)
{
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;
sieve(maxm, prime);
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;
}
public static void Main()
{
int [] arr = { 2, 3, 5, 4, 7 };
int n = arr.Length;
Console.WriteLine(countPair(arr, n));
}
}
|
PHP
<?php
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 )
{
$maxm = max( $a );
$prime = array_fill (0, $maxm + 1,0);
sieve( $maxm , $prime );
$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 ;
}
$arr = array ( 2, 3, 5, 4, 7 );
$n = count ( $arr );
echo countPair( $arr , $n );
?>
|
Javascript
<script>
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)
{
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;
sieve(maxm, prime);
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>
|
Time Complexity: O(max(n, m*log(log(m)))), where n is the size of the given array and m is the maximum element in the array.
Auxiliary Space: O(m), where m is the maximum element in the array.
Contact Us